Submission #162906

#TimeUsernameProblemLanguageResultExecution timeMemory
162906_qVp_Mag (COCI16_mag)C++14
120 / 120
577 ms168672 KiB
#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[v][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 (stderr)

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++) {
                    ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...