Submission #162903

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
162903	2019-11-10T08:47:38 Z	_qVp_	Mag (COCI16_mag)	C++14	60 / 120	584 ms	169212 KB

#include <bits/stdc++.h>
    
using namespace std;
    
const int md = 1e6 + 10;
typedef pair < long long, int > II;    

vector < int > adj[md];
int a[md], u[md], v[md], par[md];
int f[md][5];
queue < int > q;
int n;
long long a1 = 1e9, b1 = 1;
    
void compare(long long a2, long long b2) {
    if (a1 * b2 >= a2 * b1) {
        a1 = a2;
        b1 = b2;
    }
}

void dfs(int u, int root) {
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (par[u] == v) continue;
        par[v] = u;
        dfs(v, root);
        if (a[u] == 1) {
            compare(1, f[u][0] + f[v][0]);
            compare(2, f[u][0] + f[v][1]);
            compare(2, f[u][1] + f[v][0]);
            f[u][0] = max(f[u][0], f[v][0] + 1);
            f[u][1] = max(f[u][1], f[u][1] + 1);
        } else {
            compare(2, f[u][1] + f[v][0]);
            f[u][1] = max(f[u][1], f[v][0] + 1);
        }
    }

}

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; i++) 
        cin >> u[i] >> v[i];
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i < n; i++) {
        //int u, v;
        //cin >> u >> v;
        if (a[u[i]] + a[v[i]] <= 3) {
            adj[u[i]].push_back(v[i]);
            adj[v[i]].push_back(u[i]);

        }
    }
    for(int i = 1; i <= n; i++) {
        f[i][0] = (a[i] == 1);
        f[i][1] = (a[i] == 2);
    }
    for(int i = 1; i <= n; i++) 
        if (!par[i]) {
            if (a[i] >= 3) {
                compare(a[i], 1);
                continue;
            }
            //cout << i << endl;
            par[i] = i;
            dfs(i, i);
        }
    //for(int i = 1; i <= n; i++)
    //    cout << i <<" " << f[i][0] << " " << f[i][1] << endl;
    int gcd = __gcd(a1, b1);
    cout << a1 / gcd << "/" << b1 / gcd;
    return 0;
}

Compilation message

mag.cpp: In function 'void dfs(int, int)':
mag.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	23928 KB	Output is correct
2	Correct	25 ms	24056 KB	Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

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

Subtask #6
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	495 ms	91376 KB	Output is correct
2	Correct	370 ms	74120 KB	Output is correct

Subtask #7
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	497 ms	91616 KB	Output is correct
2	Correct	92 ms	32120 KB	Output is correct
3	Incorrect	584 ms	169212 KB	Output isn't correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	31864 KB	Output is correct
2	Correct	498 ms	91924 KB	Output is correct
3	Correct	384 ms	59348 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	454 ms	86864 KB	Output is correct
2	Correct	514 ms	92252 KB	Output is correct

Subtask #10
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	517 ms	92420 KB	Output is correct
2	Correct	540 ms	59384 KB	Output is correct