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
AC × 28
AC × 58
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