Submission #1354314
Source Code Expand
#include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <functional> using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define int long long int template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} typedef pair<int, int> pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; constexpr ll INF = 1001001001001001LL; constexpr ll MOD = 1000000007LL; int N, M, X, Y; // distance int bfs(vector< vector<int> > &G, int p) { int dist[1010]; fill(dist, dist+1010, INF); dist[p] = 0; queue<int> q; q.push(p); while(!q.empty()) { int t = q.front(); q.pop(); for(auto to : G[t]) { if(dist[to] > dist[t] + 1) { dist[to] = dist[t] + 1; q.push(to); } } } int dma = -1; rep(i,0,1010) if(dist[i] != INF) chmax(dma, dist[i]); return dma; } signed main() { cin >> N >> M; vector< vector<int> > G(N); rep(i,0,M) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } cin >> X >> Y; vector< vector<int> > H(X); rep(i,0,Y) { int c, d; cin >> c >> d; H[c].push_back(d); H[d].push_back(c); } int ma1 = -1, ma2 = -1, mi1 = INF, mi2 = INF; rep(i,0,N) { int val = bfs(G, i); chmax(ma1, val); chmin(mi1, val); } rep(i,0,X) { int val = bfs(H, i); chmax(ma2, val); chmin(mi2, val); } int mans = max(mi1+mi2+1, max(ma1, ma2)); printf("%lld %lld\n", mans, ma1 + ma2 + 1); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 直径 |
User | tsutaj |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2270 Byte |
Status | AC |
Exec Time | 106 ms |
Memory | 896 KB |
Judge Result
Set Name | Small | Large | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Small | 10-small_random-00, 10-small_random-01, 10-small_random-02, 10-small_random-03, 10-small_random-04, 10-small_random-05, 10-small_random-06, 10-small_random-07, 10-small_random-08, 10-small_random-09, 10-small_random-10, 10-small_random-11, 10-small_random-12, 10-small_random-13, 10-small_random-14, 10-small_random-15, 10-small_random-16, 10-small_random-17, 10-small_random-18, 10-small_random-19, 21-small_path-00, 21-small_path-01, 21-small_path-02, 21-small_path-03, 21-small_path-04, 00-sample-00, 00-sample-01, 00-sample-02 |
Large | 00-sample-00, 00-sample-01, 00-sample-02, 10-small_random-00, 10-small_random-01, 10-small_random-02, 10-small_random-03, 10-small_random-04, 10-small_random-05, 10-small_random-06, 10-small_random-07, 10-small_random-08, 10-small_random-09, 10-small_random-10, 10-small_random-11, 10-small_random-12, 10-small_random-13, 10-small_random-14, 10-small_random-15, 10-small_random-16, 10-small_random-17, 10-small_random-18, 10-small_random-19, 20-small_tree-00, 20-small_tree-01, 20-small_tree-02, 20-small_tree-03, 20-small_tree-04, 21-small_path-00, 21-small_path-01, 21-small_path-02, 21-small_path-03, 21-small_path-04, 30-large_random-00, 30-large_random-01, 30-large_random-02, 30-large_random-03, 30-large_random-04, 30-large_random-05, 30-large_random-06, 30-large_random-07, 30-large_random-08, 30-large_random-09, 40-large_comp-00, 40-large_comp-01, 40-large_comp-02, 40-large_comp-03, 40-large_comp-04, 41-large_tree-00, 41-large_tree-01, 41-large_tree-02, 41-large_tree-03, 41-large_tree-04, 42-large_path-00, 42-large_path-01, 42-large_path-02, 42-large_path-03, 42-large_path-04 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample-00 | AC | 1 ms | 256 KB |
00-sample-01 | AC | 1 ms | 256 KB |
00-sample-02 | AC | 1 ms | 256 KB |
10-small_random-00 | AC | 1 ms | 256 KB |
10-small_random-01 | AC | 1 ms | 256 KB |
10-small_random-02 | AC | 1 ms | 256 KB |
10-small_random-03 | AC | 1 ms | 256 KB |
10-small_random-04 | AC | 1 ms | 256 KB |
10-small_random-05 | AC | 1 ms | 256 KB |
10-small_random-06 | AC | 1 ms | 256 KB |
10-small_random-07 | AC | 1 ms | 256 KB |
10-small_random-08 | AC | 1 ms | 256 KB |
10-small_random-09 | AC | 1 ms | 256 KB |
10-small_random-10 | AC | 1 ms | 256 KB |
10-small_random-11 | AC | 1 ms | 256 KB |
10-small_random-12 | AC | 1 ms | 256 KB |
10-small_random-13 | AC | 1 ms | 256 KB |
10-small_random-14 | AC | 1 ms | 256 KB |
10-small_random-15 | AC | 1 ms | 256 KB |
10-small_random-16 | AC | 1 ms | 256 KB |
10-small_random-17 | AC | 1 ms | 256 KB |
10-small_random-18 | AC | 1 ms | 256 KB |
10-small_random-19 | AC | 1 ms | 256 KB |
20-small_tree-00 | AC | 2 ms | 256 KB |
20-small_tree-01 | AC | 1 ms | 256 KB |
20-small_tree-02 | AC | 2 ms | 256 KB |
20-small_tree-03 | AC | 1 ms | 256 KB |
20-small_tree-04 | AC | 27 ms | 384 KB |
21-small_path-00 | AC | 1 ms | 256 KB |
21-small_path-01 | AC | 1 ms | 256 KB |
21-small_path-02 | AC | 1 ms | 256 KB |
21-small_path-03 | AC | 1 ms | 256 KB |
21-small_path-04 | AC | 1 ms | 256 KB |
30-large_random-00 | AC | 11 ms | 512 KB |
30-large_random-01 | AC | 1 ms | 256 KB |
30-large_random-02 | AC | 3 ms | 256 KB |
30-large_random-03 | AC | 1 ms | 256 KB |
30-large_random-04 | AC | 8 ms | 384 KB |
30-large_random-05 | AC | 1 ms | 256 KB |
30-large_random-06 | AC | 4 ms | 256 KB |
30-large_random-07 | AC | 1 ms | 256 KB |
30-large_random-08 | AC | 106 ms | 896 KB |
30-large_random-09 | AC | 105 ms | 896 KB |
40-large_comp-00 | AC | 1 ms | 256 KB |
40-large_comp-01 | AC | 2 ms | 256 KB |
40-large_comp-02 | AC | 1 ms | 256 KB |
40-large_comp-03 | AC | 3 ms | 384 KB |
40-large_comp-04 | AC | 7 ms | 512 KB |
41-large_tree-00 | AC | 1 ms | 256 KB |
41-large_tree-01 | AC | 2 ms | 256 KB |
41-large_tree-02 | AC | 2 ms | 256 KB |
41-large_tree-03 | AC | 6 ms | 256 KB |
41-large_tree-04 | AC | 27 ms | 384 KB |
42-large_path-00 | AC | 3 ms | 256 KB |
42-large_path-01 | AC | 1 ms | 256 KB |
42-large_path-02 | AC | 1 ms | 256 KB |
42-large_path-03 | AC | 10 ms | 256 KB |
42-large_path-04 | AC | 21 ms | 384 KB |