oj.uz

Submission #54621

# Submission time Handle Problem Language Result Execution time Memory
54621 2018-07-04T08:23:06 Z 윤교준(#1492) Training (IOI07_training) C++11
100 / 100
 18 ms 12944 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); }
void fuk() { exit(-1); }
const bool debug = false;

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

vector<int> G[MAXN], GE[MAXN], GT[MAXN];

int dp[MAXN], dt[MAXN][1<<10], de[MAXN][MAXN], dd[MAXN][10];

int GI[MAXN][MAXN];

int prt[MAXN][10];
int dep[MAXN];

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

bitset<MAXN> isC;

int N, M, Ans;

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b] - dep[a];
	for(int i = 0; i < 10; i++) if(dt & (1<<i))
		b = prt[b][i];
	if(a == b) return a;
	for(int i = 9; ~i; i--) if(prt[a][i] != prt[b][i]) {
		a = prt[a][i]; b = prt[b][i];
	}
	return prt[a][0];
}

void f(int i) {
	for(int v : G[i]) if(!dep[v]) {
		prt[v][0] = i;
		dep[v] = dep[i] + 1;
		isC[v] = !isC[i];
		f(v);
	}
}
void g(int i) {
	for(int v : G[i]) g(v);
	int n = sz(GE[i]), m = sz(GT[i]), dg = sz(G[i]);
	//printf("i=%d, n=%d, m=%d\n", i, n, m);
	{
		int sum = 0;
		for(int j = 0; j < dg; j++)
			sum += dp[G[i][j]];
		dp[i] = sum;
		for(int key = 0; key < (1<<dg); key++)
			dt[i][key] = sum;

		for(int j = 0, a, ai; j < n; j++) {
			a = D[GE[i][j]];
			ai = GI[i][a];

			for(int key = 0; key < (1<<dg); key++) {
				if(key & (1<<ai)) continue;

				int t = dt[i][key] - dp[G[i][ai]] + de[G[i][ai]][a] + E[GE[i][j]];
				upmax(dp[i], t);
				upmax(dt[i][key | (1<<ai)], t);
			}
		}

		for(int j = 0, a, b, ai, bi; j < m; j++) {
			a = C[GT[i][j]]; b = D[GT[i][j]];
			ai = GI[i][a]; bi = GI[i][b];

			for(int key = 0; key < (1<<dg); key++) {
				if(key & ((1<<ai) | (1<<bi))) continue;

				int t = dt[i][key] - dp[G[i][ai]] + de[G[i][ai]][a] - dp[G[i][bi]] + de[G[i][bi]][b] + E[GT[i][j]];
				upmax(dp[i], t);
				upmax(dt[i][key | (1<<ai) | (1<<bi)], t);
			}
		}
	}

	for(int j = 0; j < dg; j++) {
		int &ret = dd[i][j];
		for(int key = 0; key < (1<<dg); key++) {
			if(key & (1<<j)) continue;
			upmax(ret, dt[i][key]);
		}
	}

	{
		de[i][0] = dp[i];

		for(int j = 1, ji; j <= N; j++) {
			ji = GI[i][j];
			if(i == j || ji < 0) {
				de[i][j] = dp[i];
				continue;
			}
			de[i][j] = dd[i][ji] - dp[G[i][ji]] + de[G[i][ji]][j];
		}
	}
}

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]);

	dep[1] = 1; f(1);
	for(int j = 1; j < 10; j++) for(int i = 1; i <= N; i++)
		prt[i][j] = prt[prt[i][j-1]][j-1];

	{
		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 <= M; i++) {
		F[i] = lca(C[i], D[i]);
		if(dep[C[i]] > dep[D[i]]) swap(C[i], D[i]);
		if(C[i] == F[i]) GE[F[i]].pb(i);
		else GT[F[i]].pb(i);

		//printf("Ed i=%d, %d %d %d\n", i, C[i], D[i], E[i]);
	}

	for(int i = 1; i <= N; i++) {
		vector<int> V;
		for(int v : G[i]) if(dep[i] < dep[v])
			V.pb(v);
		swap(G[i], V);
	}

	for(int i = 1; i <= N; i++)
		fill(GI[i], GI[i]+N+1, -1);

	for(int i = 1; i <= N; i++)
		for(int j = 0, n = sz(G[i]); j < n; j++)
			GI[i][G[i][j]] = j;

	for(int i = 1; i <= N; i++) {
		for(int j = i;;) {
			j = prt[j][0];
			if(!j) break;
			GI[prt[j][0]][i] = GI[prt[j][0]][j];
		}
	}

	/*
	for(int i = 1; i <= N; i++) {
        printf("%dG : ", i);
        for(int v : G[i]) printf("%d ", v);
        puts("");
	}
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= N; j++)
			printf("%d ", GI[i][j]);
		puts("");
	}
	*/

	g(1);

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

	{
		int sum = 0;
		for(int i = 1; i <= M; i++)
			sum += E[i];
		cout << (Ans + sum - dp[1]) << endl;
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 2 ms 804 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1040 KB Output is correct
2 Correct 2 ms 1168 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12620 KB Output is correct
2 Correct 17 ms 12800 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12800 KB Output is correct
2 Correct 2 ms 12800 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12800 KB Output is correct
2 Correct 2 ms 12800 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12800 KB Output is correct
2 Correct 2 ms 12800 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12800 KB Output is correct
2 Correct 5 ms 12800 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12800 KB Output is correct
2 Correct 7 ms 12800 KB Output is correct
3 Correct 9 ms 12800 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12800 KB Output is correct
2 Correct 15 ms 12800 KB Output is correct
3 Correct 14 ms 12800 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12800 KB Output is correct
2 Correct 8 ms 12800 KB Output is correct
3 Correct 18 ms 12944 KB Output is correct
4 Correct 8 ms 12944 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12944 KB Output is correct
2 Correct 18 ms 12944 KB Output is correct
3 Correct 15 ms 12944 KB Output is correct
4 Correct 17 ms 12944 KB Output is correct