Submission #37809

#	Time	Username	Problem	Language	Result	Execution time	Memory
37809		Talant	관광지 (IZhO14_shymbulak)	C++14	50 / 100	803 ms	145980 KiB

shymbulak

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e18 + 7;
const ll N = (ll)1e6 + 7;

int n;
int u[N],us[N],cn[N];
int mx;
int x,y;

vector <int> g[5005];

void dfs (int v,int o,int d = 0) {
        if (d > 0 && u[v] == d)
                cn[v] ++;

        u[v] = d;

        for (auto to : g[v]) {
                if (!u[to] && o != to)
                        dfs(to,o,d + 1);
                else if (u[to] >= d + 1) {
                        dfs(to,o,d + 1);
                }
        }
}

int main () {
        cin >> n;

        for (int i = 1; i <= n; i ++) {
                cin >> x >> y;
                g[x].pb(y);
                g[y].pb(x);
        }

        for (int i = 1; i <= n; i ++)
                cn[i] = 1;

        for (int i = 1; i <= n; i ++) {
                dfs(i,i);
                for (int i = 1; i <= n; i ++) {
                        mx = max(mx,u[i]);
                        us[u[i]] += cn[i];
                        u[i] = 0;
                        cn[i] = 1;
                }
        }
        cout << us[mx] / 2 << endl;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50