oj.uz

답안 #92799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92799 2019-01-04T22:08:56 Z updown1 Mag (COCI16_mag) C++17
60 / 120
 526 ms 170372 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) {
        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) {
        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
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 24056 KB Output is correct
2 Incorrect 23 ms 23928 KB Output isn't correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 24056 KB Output is correct
2 Incorrect 23 ms 23928 KB Output isn't correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 394 ms 109824 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23800 KB Output is correct
2 Incorrect 526 ms 167388 KB Output isn't correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 512 ms 166772 KB Output is correct

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 419 ms 89800 KB Output is correct
2 Incorrect 314 ms 72440 KB Output isn't correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 406 ms 92896 KB Output is correct
2 Correct 80 ms 30584 KB Output is correct
3 Correct 476 ms 170372 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 30576 KB Output is correct
2 Correct 425 ms 90360 KB Output is correct
3 Correct 349 ms 57668 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 376 ms 87152 KB Output is correct
2 Correct 390 ms 90836 KB Output is correct

Subtask #10
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 446 ms 90568 KB Output isn't correct
2 Halted 0 ms 0 KB -