oj.uz

Submission #47100

# Submission time Handle Problem Language Result Execution time Memory
47100 2018-04-27T15:02:38 Z diegogrc Mag (COCI16_mag) C++17
84 / 120
 508 ms 95384 KB 
//  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.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 58596 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 58596 KB Output is correct
2 Correct 508 ms 82132 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 82132 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 82264 KB Output is correct
2 Correct 343 ms 82264 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 94716 KB Output is correct
2 Incorrect 93 ms 94716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 94716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 94716 KB Output is correct
2 Correct 460 ms 94716 KB Output is correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 95384 KB Output is correct
2 Incorrect 371 ms 95384 KB Output isn't correct