답안 #54567 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54567	2018-07-04T06:18:39 Z	윤교준(#1492)	Training (IOI07_training)	C++11	30 / 100	4 ms	764 KB

training

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)))
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fuk() { exit(-1); }
const bool debug = false;

const int MAXN = 1005;
const int MAXM = 5005;

vector<int> G[MAXN];

int dp[MAXN];
int S[MAXN];

int dep[MAXN];

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

bitset<MAXN> isC;

int N, M, Ans;

void f(int i) {
	for(int v : G[i]) if(!dep[v]) {
		dep[v] = dep[i] + 1;
		isC[v] = !isC[i];
		f(v);
	}
}

int main() {
    //freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	{
		vector<pii> VA;
		vector<pair<pii, int>> VB;

		for(int i = 1, a, b, c; i <= M; i++) {
			cin >> a >> b >> c;
			if(a == b) fuk();
			if(!c) {
				VA.eb(a, b);
			} else {
				VB.eb(pii(a, b), c);
			}
		}

		for(int i = 1; i < N; i++)
			tie(A[i], B[i]) = VA[i-1];

		M -= N-1;
		for(int i = 1; i <= M; i++) {
			tie(C[i], D[i]) = VB[i-1].first;
			E[i] = VB[i-1].second;
		}
	}

	for(int i = 1; i < N; i++)
		fg(G, A[i], B[i]);

	{
		int si;
		for(si = 1; si <= N && sz(G[si]) != 1; si++);
		if(N < si) fuk();

		dep[si] = 1;
		f(si);
	}

	for(int i = 1; i <= N; i++) for(int j = i+1; j <= N; j++)
		if(dep[i] == dep[j]) fuk();

    if(debug) {
        for(int i = 1; i <= N; i++)
            printf("%d : %d %d\n", i, int(isC[i]), dep[i]);
    }

	{
		vector<pair<pii, int>> V;
		for(int i = 1; i <= M; i++) {
			if(isC[C[i]] != isC[D[i]]) {
				Ans += E[i];
				continue;
			}
			V.eb(pii(C[i], D[i]), E[i]);
		}

		M = sz(V);
		for(int i = 1; i <= M; i++) {
			tie(C[i], D[i]) = V[i-1].first;
			E[i] = V[i-1].second;
		}
	}

	if(debug) {
        for(int i = 1; i <= M; i++)
            printf("%d : %d %d %d\n", i, C[i], D[i], E[i]);
    }

	for(int i = 1; i < N; i++) {
		A[i] = dep[A[i]];
		B[i] = dep[B[i]];
		if(A[i] > B[i]) swap(A[i], B[i]);
	}
	for(int i = 1; i <= M; i++) {
		C[i] = dep[C[i]];
		D[i] = dep[D[i]];
		if(C[i] > D[i]) swap(C[i], D[i]);
	}

	for(int i = 1; i <= M; i++)
		S[C[i]] += E[i];
	for(int i = N; i; i--)
		S[i] += S[i+1];

	for(int i = 1; i <= N; i++) G[i].clear();
	for(int i = 1; i <= M; i++) G[C[i]].pb(i);

	for(int i = N; i; i--) {
		int &ret = dp[i], sum = 0;
		for(int v : G[i]) sum += E[v];
		ret = dp[i+1] + sum;

		for(int v : G[i])
			upmin(ret, dp[D[v]] + S[i] - S[D[v]] - E[v]);
	}

	if(debug) {
        for(int i = 1; i <= N; i++)
            printf("%d : %d\n", i, dp[i]);
	}

	cout << (dp[1] + Ans) << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	484 KB	Output is correct
2	Correct	2 ms	616 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	680 KB	Output is correct
2	Correct	3 ms	736 KB	Output is correct

Subtask #4
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	736 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	736 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	736 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	736 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	736 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3 ms	744 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	4 ms	760 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	4 ms	764 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

답안 #54567

Compilation message