oj.uz

Submission #54563

# Submission time Handle Problem Language Result Execution time Memory
54563 2018-07-04T06:00:43 Z 윤교준(#1492) Training (IOI07_training) C++11
0 / 100
 4 ms 720 KB 
#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); }

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(!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; sz(G[si]) != 1; si++);

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

	{
		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;
		}
	}

	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]+1] + S[i] - S[D[v]+1] - E[v]);
	}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 720 KB Output isn't correct
2 Halted 0 ms 0 KB -