oj.uz

Submission #92800

# Submission time Handle Problem Language Result Execution time Memory
92800 2019-01-04T22:20:09 Z updown1 Mag (COCI16_mag) C++17
120 / 120
 487 ms 153024 KB 
/*
https://github.com/mostafa-saad/MyCompetitiveProgramming/blob/master/Olympiad/COCI/official/2017/contest1_solutions/solutions.pdf
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=1000000, INF=1000000000;
///500,000,000
int N, val[MAXN], sm = INF, dp[MAXN], o1, o2, dp1[MAXN], n1[MAXN], dp2[MAXN];
vector<int> adj[MAXN];

void go (int at, int par) {
    int b1=0, b2=0;
    if (val[at] == 1) dp[at] = 1;
    for (int i: adj[at]) if (i != par) {
        go(i, at);
        if (val[at] == 1) dp[at] = max(dp[at], 1+dp[i]);
        if (dp[i] > b2) {
            b2 = dp[i];
            if (b2 > b1) swap(b1, b2);
        }
    }
    if (val[at] == 1) o1 = max(o1, b1+b2+1);
}
void go2(int at, int par) {
    for (int i: adj[at]) if (i != par && val[i] == 1) {
        if (dp[i] > dp1[at]) {
            dp2[at] = dp1[at];
            dp1[at] = dp[i];
            n1[at] = i;
        }
        else if (dp[i] > dp2[at]) dp2[at] = dp[i];
    }
    if (par != -1 && val[par] == 1) {
        int x;
        if (n1[par] == at) x = dp2[par];
        else x = dp1[par];
        if (x > dp1[at]) {
            dp2[at] = dp1[at];
            dp1[at] = x;
            n1[at] = par;
        }
        else if (x > dp2[at]) dp2[at] = x;
    }
    if (val[at] == 1) {dp1[at]++; dp2[at]++;}
    if (val[at] == 2) o2 = max(o2, dp2[at]);
    for (int i: adj[at]) if (i != par) go2(i, at);
}

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	For (i, 1, N) {int a, b; cin >> a >> b; a--; b--; adj[a].pb(b); adj[b].pb(a);}
	ffi {n1[i] = -1; cin >> val[i]; sm = min(sm, val[i]);}
	if (sm != 1) {
        w<< sm <<"/1"<<e;
        return 0;
	}
	go(0, -1);
	go2(0,-1);
	if (o2 == o1) w<< "2/" << 2*o2+1<<e;
	else w<< "1/" << o1<<e;
}

Compilation message

mag.cpp:63:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23940 KB Output is correct
2 Correct 22 ms 23928 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 96680 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 486 ms 152736 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 149780 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 75080 KB Output is correct
2 Correct 335 ms 61928 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 75532 KB Output is correct
2 Correct 102 ms 29688 KB Output is correct
3 Correct 486 ms 153024 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 29432 KB Output is correct
2 Correct 433 ms 75340 KB Output is correct
3 Correct 438 ms 50308 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 71660 KB Output is correct
2 Correct 408 ms 73748 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 75512 KB Output is correct
2 Correct 395 ms 57480 KB Output is correct