Submission #47100

#	Time	Username	Problem	Language	Result	Execution time	Memory
47100		diegogrc	Mag (COCI16_mag)	C++17	84 / 120	508 ms	95384 KiB

mag

//  Copyright © 2018 Diego Garcia Rodriguez del Campo. All rights reserved.

#include<bits/stdc++.h>
#define MAX 1000005
#define optimiza_io cin.tie(0); ios_base::sync_with_stdio(0);
using namespace std;
typedef long long i64;

int N, men, ansa, ansb;
int v[MAX];
vector < int > ady[MAX];
int id[MAX];
int sz[MAX];


void check( int a , int b )
{
    if( a * ansb < ansa * b )
    {
        ansa = a, ansb = b;
        if( ansb % ansa == 0 )
            ansb /= ansa, ansa = 1;
    }
}

int uf( int x )
{
    if( x == id[x] )
        return x;
    return id[x] = uf( id[x] );
}

int main()
{
    optimiza_io
    cin >> N;
    for( int i = 1; i < N; i ++ )
    {
        int a, b;
        cin >> a >> b;
        ady[a].push_back( b );
        ady[b].push_back( a );
    }
    for( int i = 1; i <= N; i ++ )
    {
        cin >> v[i];
        if( men > v[i] or i == 1 )
            men = v[i];
    }
    if( men > 1 )
    {
        cout << men << "/1\n";
        return 0;
    }
    for( int i = 1; i <= N; i ++ )
        id[i] = i, sz[i] = 1;
    for( int i = 1; i <= N; i ++ )
        if( v[i] == 1 )
            for( auto x : ady[i] )
                if( v[x] == 1 && uf( i ) != uf( x ) )
                    sz[uf( i )] += sz[uf( x )], id[uf( x )] = id[uf( i )];
    ansa = ansb = 1;
    for( int i = 1; i <= N; i ++ )
    {
        if( v[i] == 1 )
            check( 1 , sz[uf( i )] );
        else
        {
            int tama = 0, tamb = 0;
            for( auto j : ady[i] )
            {
                if( v[j] == 1 && tama < sz[uf( j )] )
                    tamb = tama, tama = sz[uf( j )];
                else if( v[j] == 1 && tamb < sz[uf( j )] )
                    tamb = sz[uf( j )];
            }
            check( v[i] , tama + tamb + 1 );
        }
    }
    cout << ansa << "/" << ansb << "\n";
    return 0;
}

• 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: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 12 / 12
• Subtask 10: 0 / 12