Submission #167576

#	Time	Username	Problem	Language	Result	Execution time	Memory
167576		combi1k1	Mag (COCI16_mag)	C++14	120 / 120	501 ms	96428 KiB

mag

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12