oj.uz

Submission #54550

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

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

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

int fir, sec;

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

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

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

int subdp (int S, int E) {
	if(S > E) return 0;
	if(~sub[S][E]) return sub[S][E];
	sub[S][E] = subdp(S+1, E) + val[S][S];
	for(int i=S+1;i<=E;i++) {
		sub[S][E] = max(sub[S][E], subdp(S+1, i-1) + subdp(i+1, E) + val[S][i]);
	}
	return sub[S][E];
}

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++) {
			sub[i][j] = -1;
			val[i][j] = 0;
		}
		if(T == P) {
			val[i][i] = 0;
		}
		else {
			sum[C] += dt[T];
			val[i][i] = dt[T];
		}
	}
	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(0, S-1);
	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];
		getfns(a[i].a, 0, a[i].b);
		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
0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #6
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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