Submission #47099

#	Time	Username	Problem	Language	Result	Execution time	Memory
47099		diegogrc	Mag (COCI16_mag)	C++17	12 / 120	508 ms	180236 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, tam;
int v[MAX];
vector < int > ady[MAX];
int id[MAX];
int sz[MAX];

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 )];
    for( int i = 1; i <= N; i ++ )
        if( v[i] == 1 )
            tam = max( tam , sz[uf( i )] );
    cout << "1/" << tam << "\n";
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12