oj.uz

Submission #262783

# Submission time Handle Problem Language Result Execution time Memory
262783 2020-08-13T08:53:21 Z 송준혁(#5085) Training (IOI07_training) C++17
82 / 100
 300 ms 9600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, sum;
int U[5050], V[5050], W[5050];
int dep[5050], D[5050][1030];
int E[1010][1010], P[1010];
bool chk[5050][1030];
vector<int> adj[1010], V1[1010], V2[1010], C[1010];

void dfs(int u, int p){
	P[u] = p;
	for (int v : adj[u]){
		if (v == p) continue;
		dep[v] = dep[u]+1;
		dfs(v, u);
	}
}

int dp(int u, int b){
	if (chk[u][b]) return D[u][b];
	chk[u][b] = true;
	for (int i=0; i<C[u].size(); i++){
		int nb=b, k=C[u][i], x;
		if (V1[u][i] != u){
			x = E[V1[u][i]][u];
			k += dp(V1[u][i], 0);
			for (int v=V1[u][i]; P[v]!=u; v=P[v]) k += dp(P[v], (1<<E[V1[u][i]][P[v]]));
			if (b & (1<<x)) continue;
			nb |= (1<<x);
		}
		if (V2[u][i] != u){
			x = E[V2[u][i]][u];
			k += dp(V2[u][i], 0);
			for (int v=V2[u][i]; P[v]!=u; v=P[v]) k += dp(P[v], (1<<E[V2[u][i]][P[v]]));
			if (b & (1<<x)) continue;
			nb |= (1<<x);
		}
		D[u][b] = max(D[u][b], dp(u, nb)+k);
	}
	int k=0;
	for (int i=0; i<adj[u].size(); i++) if (!((1<<i)&b) && adj[u][i] != P[u]) k += dp(adj[u][i], 0);
	D[u][b] = max(D[u][b], k);
	return D[u][b];
}

int main(){
	scanf("%d %d", &N, &M);
	for (int i=1; i<=M; i++){
		scanf("%d %d %d", &U[i], &V[i], &W[i]);
		if (!W[i]){
			adj[U[i]].push_back(V[i]);
			adj[V[i]].push_back(U[i]);
		}
		sum += W[i];
	}
	dfs(1, 0);
	for (int i=1; i<=M; i++){
		if ((dep[U[i]]^dep[V[i]])&1) continue;
		int u=U[i], v=V[i];
		while (u != v){
			if (dep[u] >= dep[v]){
				for (int j=0; j<adj[P[u]].size(); j++){
					if (adj[P[u]][j] == u){
						E[U[i]][P[u]] = j;
						break;
					}
				}
				u = P[u];
			}
			else{
				for (int j=0; j<adj[P[v]].size(); j++){
					if (adj[P[v]][j] == v){
						E[V[i]][P[v]] = j;
						break;
					}
				}
				v = P[v];
			}
		}
		V1[u].push_back(U[i]);
		V2[u].push_back(V[i]);
		C[u].push_back(W[i]);
	}
	printf("%d\n", sum-dp(1, 0));
	return 0;
}

Compilation message

training.cpp: In function 'int dp(int, int)':
training.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i=0; i<C[u].size(); i++){
      |                ~^~~~~~~~~~~~
training.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i=0; i<adj[u].size(); i++) if (!((1<<i)&b) && adj[u][i] != P[u]) k += dp(adj[u][i], 0);
      |                ~^~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int j=0; j<adj[P[u]].size(); j++){
      |                   ~^~~~~~~~~~~~~~~~~
training.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int j=0; j<adj[P[v]].size(); j++){
      |                   ~^~~~~~~~~~~~~~~~~
training.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
training.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d %d %d", &U[i], &V[i], &W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9216 KB Output is correct
2 Correct 22 ms 9088 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 166 ms 5016 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9600 KB Output is correct
2 Correct 56 ms 9496 KB Output is correct
3 Correct 14 ms 9472 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4608 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Execution timed out 1094 ms 9592 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 9592 KB Output is correct
2 Execution timed out 1084 ms 8320 KB Time limit exceeded
3 Halted 0 ms 0 KB -