oj.uz

Submission #54571

# Submission time Handle Problem Language Result Execution time Memory
54571 2018-07-04T06:38:32 Z khsoo01 Training (IOI07_training) C++11
100 / 100
 70 ms 8700 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][N], sz[N], dt[N][1<<11], val[11][11];

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

void solve (int C, int P) {
	for(auto &T : adj[C]) {
		if(T == P) continue;
		solve(T, C);
	}
	int S = (int)adj[C].size();
	sz[C] = S;
	for(int i=0;i<S;i++) {
		int T = adj[C][i];
		idx[C][T] = i;
		for(int j=0;j<S;j++) {
			val[i][j] = 0;
		}
		if(T != P) val[i][i] = dt[T][(1<<sz[T])-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[C][X]);
				continue;
			}
			for(int i=X,j=-1;;i=par[i]) {
				int I = (1<<sz[i]) - 1 - (1<<idx[i][par[i]]);
				if(j != -1) I -= (1<<idx[i][j]);
				V += dt[i][I];
				j = i;
				if(par[i] == C) {
					Z.push_back(idx[C][i]);
					break;
				}
			}
		}
		sort(Z.begin(), Z.end());
		val[Z[0]][Z[1]] = max(val[Z[0]][Z[1]], V);
	}
	for(int i=1;i<(1<<S);i++) {
		int F = -1;
		for(int j=0;j<S;j++) {
			if(!(i & (1<<j))) continue;
			if(F == -1) F = j;
			dt[C][i] = max(dt[C][i], val[F][j] + dt[C][i-((1<<F)|(1<<j))]);
		}
	}
}

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][(1<<sz[1])-1]);
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:99: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:101: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 3 ms 504 KB Output is correct
2 Correct 3 ms 612 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8588 KB Output is correct
2 Correct 41 ms 8616 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8616 KB Output is correct
2 Correct 6 ms 8616 KB Output is correct

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8616 KB Output is correct
2 Correct 30 ms 8616 KB Output is correct
3 Correct 43 ms 8616 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8616 KB Output is correct
2 Correct 13 ms 8616 KB Output is correct
3 Correct 41 ms 8700 KB Output is correct
4 Correct 15 ms 8700 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8700 KB Output is correct
2 Correct 70 ms 8700 KB Output is correct
3 Correct 39 ms 8700 KB Output is correct
4 Correct 37 ms 8700 KB Output is correct