oj.uz

Submission #37809

# Submission time Handle Problem Language Result Execution time Memory
37809 2017-12-28T06:59:06 Z Talant Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 803 ms 145980 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 13852 KB Output is correct
2 Correct 0 ms 13852 KB Output is correct
3 Correct 0 ms 13852 KB Output is correct
4 Correct 0 ms 13852 KB Output is correct
5 Correct 0 ms 13852 KB Output is correct
6 Correct 0 ms 13852 KB Output is correct
7 Correct 0 ms 13852 KB Output is correct
8 Correct 0 ms 13852 KB Output is correct
9 Correct 0 ms 13852 KB Output is correct
10 Correct 0 ms 13852 KB Output is correct
11 Correct 0 ms 13852 KB Output is correct
12 Correct 0 ms 13852 KB Output is correct
13 Correct 0 ms 13852 KB Output is correct
14 Correct 3 ms 13852 KB Output is correct
15 Correct 3 ms 13852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13852 KB Output is correct
2 Correct 6 ms 13852 KB Output is correct
3 Correct 19 ms 13852 KB Output is correct
4 Correct 19 ms 13852 KB Output is correct
5 Correct 659 ms 13984 KB Output is correct
6 Correct 296 ms 14116 KB Output is correct
7 Correct 606 ms 13984 KB Output is correct
8 Correct 526 ms 13984 KB Output is correct
9 Correct 726 ms 13984 KB Output is correct
10 Correct 803 ms 13984 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 145980 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -