oj.uz

Submission #167572

# Submission time Handle Problem Language Result Execution time Memory
167572 2019-12-09T03:00:07 Z combi1k1 Mag (COCI16_mag) C++14
36 / 120
 4000 ms 97104 KB 
#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second

const int   N   = 1e6 + 1;

typedef pair<int,int>   ii;

int f[N];
int a[N];
int v[N];

vector<int> g[N];

void dfs(int u,int p)   {
    f[u] = 1;
    for(int v : g[u])   if (v ^ p)  {
        dfs(v,u);
        f[u] = max(f[u],f[v] + 1);
    }
}
void cal(int u,int p,int lz)    {
    f[u] = max(f[u],lz + 1);

    int mx1 = lz;
    int mx2 = 0;

    for(int v : g[u])   if (v ^ p)  {
        if (mx2 < f[v])
            mx2 = f[v];
        if (mx1 < mx2)
            swap(mx1,mx2);
    }
    for(int v : g[u])   if (v ^ p)  {
        if (f[v] == mx1)
            cal(v,u,mx2 + 1);
        else
            cal(v,u,mx1 + 1);
    }
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    vector<ii>  E;

    for(int i = 2 ; i <= n ; ++i)   {
        int x;  cin >> x;
        int y;  cin >> y;

        E.push_back(ii(x,y));
    }

    int ans = 1e9;

    for(int i = 1 ; i <= n ; ++i)   {
        cin >> a[i];
        ans = min(ans,a[i]);
    }

    if (ans > 1)    {
        cout << ans << "/1";
        return  0;
    }

    for(ii  e : E)  {
        int x = e.X;
        int y = e.Y;
        if (a[x] == 1 && a[y] == 1) {
            g[x].push_back(y);
            g[y].push_back(x);
        }
    }
    for(int i = 1 ; i <= n ; ++i)   if(!v[i])
        dfs(i,0),
        cal(i,0,0);

    int num = 1;
    int den = 1;

    for(int i = 1 ; i <= n ; ++i)
        if (den < f[i])
            den = f[i];

    for(ii  e : E)  {
        int x = e.X;
        int y = e.Y;
        if (a[x] < 2 && a[y] < 2)
            continue;
        if (a[x] > 3)   continue;
        if (a[y] > 3)   continue;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    for(int i = 1 ; i <= n ; ++i)   if (a[i] == 2)  {
        int len = 1;
        int Max = 1;

        for(int x : g[i])   {
            len = max(len,f[x] + Max);
            Max = max(Max,f[x] + 1);
        }

        if (num * len > 2 * den)    {
            num = 2;
            den = len;
        }
    }

    cout << num << "/" << den << endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 25 ms 23928 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4018 ms 97104 KB Time limit exceeded

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 545 ms 74408 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4025 ms 69716 KB Time limit exceeded

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 71400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 75984 KB Output is correct
2 Execution timed out 4086 ms 30188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4085 ms 29396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4030 ms 64292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4025 ms 74760 KB Time limit exceeded
2 Halted 0 ms 0 KB -