oj.uz

Submission #47099

# Submission time Handle Problem Language Result Execution time Memory
47099 2018-04-27T14:54:21 Z diegogrc Mag (COCI16_mag) C++17
12 / 120
 508 ms 180236 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, 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.0 / 12.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 421 ms 72596 KB Output isn't correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 459 ms 97080 KB Output isn't correct

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

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

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 144000 KB Output is correct
2 Incorrect 508 ms 164004 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 180236 KB Output is correct
2 Incorrect 383 ms 180236 KB Output isn't correct