oj.uz

Submission #167576

# Submission time Handle Problem Language Result Execution time Memory
167576 2019-12-09T03:05:57 Z combi1k1 Mag (COCI16_mag) C++14
120 / 120
 501 ms 96428 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;
	v[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 23 ms 23928 KB Output is correct
2 Correct 24 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 24 ms 23928 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 96428 KB Output is correct

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 75436 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 74752 KB Output is correct
2 Correct 363 ms 64324 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 76000 KB Output is correct
2 Correct 88 ms 29296 KB Output is correct
3 Correct 486 ms 78548 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 29276 KB Output is correct
2 Correct 482 ms 79248 KB Output is correct
3 Correct 391 ms 55904 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 72004 KB Output is correct
2 Correct 485 ms 78540 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 75384 KB Output is correct
2 Correct 367 ms 56544 KB Output is correct