oj.uz

답안 #132761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132761 2019-07-19T13:30:48 Z youngyojun Designated Cities (JOI19_designated_cities) C++11
7 / 100
 358 ms 34272 KB 
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;

const int MAXN = 200055;

vector<int> G[MAXN];
int prt[MAXN], dep[MAXN], cnt[MAXN], dfo[MAXN];

int A[MAXN], B[MAXN], C[MAXN], D[MAXN];

ll Ans[MAXN], Sum;
int N, Q;

void predfs(int i, int &c) {
	cnt[i] = 1; dfo[i] = ++c;
	for(int e : G[i]) {
		int v = A[e]^B[e]^i;
		if(v == prt[i]) continue;
		dep[v] = dep[i] + 1;
		prt[v] = i;
		predfs(v, c);
		cnt[i] += cnt[v];
	}
}

void dfsOne(int i, ll sum) {
	if(Ans[1] < sum) Ans[1] = sum;
	for(int e : G[i]) if(A[e] != prt[i])
		dfsOne(B[e], sum - D[e] + C[e]);
}

void getAnsOne() {
	{ int c = 0; predfs(1, c); }
	for(int i = 1; i < N; i++) if(prt[A[i]] == B[i]) {
		swap(A[i], B[i]);
		swap(C[i], D[i]);
	}
	ll sum = 0;
	for(int i = 1; i < N; i++) sum += D[i];
	dfsOne(1, sum);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i < N; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
		Sum += C[i] + D[i];
	}

	getAnsOne();

	cin >> Q;
	for(int a; Q--;) {
		cin >> a;
		printf("%lld\n", Sum - Ans[a]);
	}
	return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 303 ms 24004 KB Output is correct
3 Correct 358 ms 34100 KB Output is correct
4 Correct 277 ms 22648 KB Output is correct
5 Correct 281 ms 24152 KB Output is correct
6 Correct 297 ms 25380 KB Output is correct
7 Correct 244 ms 24432 KB Output is correct
8 Correct 355 ms 34272 KB Output is correct
9 Correct 192 ms 24712 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 303 ms 24004 KB Output is correct
3 Correct 358 ms 34100 KB Output is correct
4 Correct 277 ms 22648 KB Output is correct
5 Correct 281 ms 24152 KB Output is correct
6 Correct 297 ms 25380 KB Output is correct
7 Correct 244 ms 24432 KB Output is correct
8 Correct 355 ms 34272 KB Output is correct
9 Correct 192 ms 24712 KB Output is correct
10 Incorrect 6 ms 5112 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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