oj.uz

Submission #54605

# Submission time Handle Problem Language Result Execution time Memory
54605 2018-07-04T07:54:59 Z 윤교준(#1492) Training (IOI07_training) C++11
0 / 100
 16 ms 8768 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], de[MAXN][MAXN], dd[MAXN][15];

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 &ret = dp[i];
		for(int key = 0; key < (1<<n); key++) {
			int used = 0, sum = 0;
			{
				bool flag = false;
				for(int j = 0, t, ti; j < n; j++) if(key & (1<<j)) {
					ti = GI[i][D[GE[i][j]]];
					t = (1 << ti);
					if(used & t) {
						flag = true;
						break;
					}
					used |= t;
					sum += E[GE[i][j]] + de[G[i][ti]][D[GE[i][j]]];
				}
				if(flag) continue;
			}
			for(int j = 0; j < dg; j++) if(!(used & (1<<j)))
				sum += dp[G[i][j]];
			//printf("i=%d, key=%d, sum=%d\n", i, key, sum);
			upmax(ret, sum);
			for(int j = 0; j < dg; j++) if(!(used & (1<<j)))
                upmax(dd[i][j], sum);

			for(int j = 0, a, b, ai, bi, t; j < m; j++) {
				a = C[GT[i][j]]; b = D[GT[i][j]];
				ai = GI[i][a]; bi = GI[i][b];
				if((used & (1<<ai)) || (used & (1<<bi))) continue;
				t = sum - dp[G[i][ai]] - dp[G[i][bi]] + de[G[i][ai]][a] + de[G[i][bi]][b] + E[GT[i][j]];
				//printf("i=%d, j=%d : a=%d, b=%d :: %d\n", i, j, a, b, t);
				upmax(ret, t);
				for(int k = 0; k < dg; k++) if(!((used | (1<<ai) | (1<<bi)) & (1<<k)))
                    upmax(dd[i][k], t);
			}
		}
	}

	{
		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[GI[i][ji]] + de[GI[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
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8628 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 8628 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 8628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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