oj.uz

Submission #54560

# Submission time Handle Problem Language Result Execution time Memory
54560 2018-07-04T05:41:04 Z 나는김현수(#2054) Training (IOI07_training) C++11
30 / 100
 33 ms 936 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1005, M = 5005, inf = 1e9;

int n, m, par[N], dfn[N], inv[N], all, cc;

int idx[N], dt[N], sum[N], sub[1<<10], val[15][15];

int fir, sec, len;

vector<int> adj[N], edg[N];

struct edge {
	int a, b, v;
} a[M];

void calc (int C, int P) {
	par[C] = P;
	dfn[C] = ++cc;
	inv[cc] = C;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
}

bool getfns (int C, int P, int O) {
	bool F = false;
	if(C == O) F = true;
	else {
		for(auto &T : adj[C]) {
			if(T == P) continue;
			if(getfns(T, C, O)) {
				F = true;
				break;
			}
		}
	}
	if(F) {
		if(dfn[fir] > dfn[C]) {
			sec = fir;
			fir = C;
		}
		else if(dfn[sec] > dfn[C]) {
			sec = C;
		}
		len++;
	}
	return F;
}

int subdp (int B, int S) {
	if(~sub[B]) return sub[B];
	int F = -1;
	for(int i=0;i<S;i++) {
		if(!(B & (1<<i))) continue;
		if(F == -1) F = i;
		sub[B] = max(sub[B], val[F][i] + subdp(B - ((1<<F) | (1<<i)), S));
	}
	return sub[B];
}

void solve (int C, int P) {
	for(auto &T : adj[C]) {
		if(T == P) continue;
		solve(T, C);
	}
	int S = (int)adj[C].size();
	for(int i=0;i<S;i++) {
		int T = adj[C][i];
		idx[T] = i;
		for(int j=0;j<S;j++) {
			val[i][j] = 0;
		}
		if(T == P) continue;
		sum[C] += dt[T];
		val[i][i] = dt[T];
	}
	for(int i=1;i<(1<<S);i++) {
		sub[i] = -1;
	}
	for(auto &T : edg[C]) {
		vector<int> Z;
		int V = a[T].v;
		for(auto &X : {a[T].a, a[T].b}) {
			if(X == par[C]) {
				Z.push_back(idx[X]);
				continue;
			}
			for(int i=X;;i=par[i]) {
				V += sum[i];
				if(par[i] == C) {
                    V += dt[i];
					Z.push_back(idx[i]);
					break;
				}
			}
		}
		sort(Z.begin(), Z.end());
		val[Z[0]][Z[1]] = max(val[Z[0]][Z[1]], V);
	}
	dt[C] = subdp((1<<S)-1, S);
	sum[C] -= dt[C];
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].v);
		if(!a[i].v) {
			adj[a[i].a].push_back(a[i].b);
			adj[a[i].b].push_back(a[i].a);
		}
		all += a[i].v;
	}
	calc(1, 0);
	for(int i=1;i<=m;i++) {
		if(!a[i].v) continue;
		if(dfn[a[i].a] > dfn[a[i].b]) {
			swap(a[i].a, a[i].b);
		}
		fir = sec = inv[n];
		len = 0;
		getfns(a[i].a, 0, a[i].b);
		if(len % 2 == 0) continue;
		if(fir == a[i].a) {
			edg[sec].push_back(i);
		}
		else {
			edg[fir].push_back(i);
		}
	}
	solve(1, 0);
	printf("%d\n", all - dt[1]);
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
training.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].v);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 728 KB Output is correct
2 Correct 26 ms 936 KB Output is correct

Subtask #4
0 / 7.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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