oj.uz

Submission #575157

# Submission time Handle Problem Language Result Execution time Memory
575157 2022-06-09T19:23:53 Z Antekb Training (IOI07_training) C++14
100 / 100
 42 ms 24500 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using pii = pair<int, int>;
const int K=10, N=1<<K;
vector<int> E[N], lca[N];
int id[N], d[N], par[N], pre[N], post[N];
int wsk;
int dp[N][1<<K];
int dp2[N][5*N];
int n, m;
vector<pair<int, pii > > edg, edg2;
vector<int> dob;
void dfs(int v, int p){
	pre[v]=wsk++;
	par[v]=p;
	d[v]=d[p]+1;
	for(int i=0; i<E[v].size(); i++)if(E[v][i]==p)swap(E[v][i], E[v].back());
	if(p!=0)E[v].pop_back();
	for(int i=0; i<E[v].size(); i++){
		id[E[v][i]]=i;
		dfs(E[v][i], v);
	}
	post[v]=wsk;
}
void dfs2(int v){
	for(int u:E[v]){
		dfs2(u);
		dp[v][1<<id[u]]=dp2[u][0];
	}
	for(int e:lca[v]){
		int u=edg[e].nd.st, w=edg[e].nd.nd;
		while(par[w]!=v)w=par[w];
		if(u==v){
			dp[v][1<<id[w]]=max(edg[e].st + dp2[w][e], dp[v][1<<id[w]]);
		}
		else{
			while(par[u]!=v)u=par[u];
			dp[v][(1<<id[u])+(1<<id[w])]=max(edg[e].st+dp2[u][e]+dp2[w][e], dp[v][(1<<id[u])+(1<<id[w])]);
		}
	}
	for(int i=0; i<(1<<E[v].size()); i++){
		for(int j=i; ; j=(j-1)&i){
			dp[v][i]=max(dp[v][i], dp[v][j]+dp[v][i-j]);
			if(j==0)break;
		}
	}
	for(int e:dob){
		if(edg[e].nd.st==v && pre[edg[e].nd.nd]>=post[v]){
			dp2[v][e]=dp[v][(1<<E[v].size())-1];
		}
		if(edg[e].nd.nd==v){
			dp2[v][e]=dp[v][(1<<E[v].size())-1];
		}
		if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
			if(par[edg2[e].nd.st]==v){
				dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]+dp2[edg2[e].nd.st][e];
				edg2[e].nd.st=v;
			}
			if(par[edg2[e].nd.nd]==v){
				dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.nd])]+dp2[edg2[e].nd.nd][e];
				edg2[e].nd.nd=v;
			}
		}
	}
	dp2[v][0]=dp[v][(1<<E[v].size())-1];
}
int main(){
	cin>>n>>m;
	int sum=0;
	for(int i=0; i<m; i++){
		int u, v, w;
		cin>>u>>v>>w;
		sum+=w;
		edg.push_back({w, {u, v}});
		if(w==0){
			E[u].push_back(v);
			E[v].push_back(u);
		}
	}
	dfs(1, 0);
	sort(edg.begin(), edg.end());
	for(int i=n-1; i<m; i++){
		if(pre[edg[i].nd.st]>pre[edg[i].nd.nd])swap(edg[i].nd.st, edg[i].nd.nd);
		int u=edg[i].nd.st, v=edg[i].nd.nd;
		if((d[u]&1)!=(d[v]&1)){
			continue;
		}
		if(d[u]<d[v])swap(u, v);
		while(d[u]>d[v]){
			u=par[u];
		}
		while(u!=v){
			u=par[u];
			v=par[v];
		}
		dob.push_back(i);
		lca[u].push_back(i);
	}
	edg2=edg;
	dfs2(1);
	cout<<sum-dp2[1][0];
}

Compilation message

training.cpp: In function 'void dfs(int, int)':
training.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0; i<E[v].size(); i++)if(E[v][i]==p)swap(E[v][i], E[v].back());
      |               ~^~~~~~~~~~~~
training.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~
training.cpp: In function 'void dfs2(int)':
training.cpp:56:24: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   56 |   if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
      |      ~~~~~~~~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20604 KB Output is correct
2 Correct 17 ms 20628 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8404 KB Output is correct
2 Correct 8 ms 8276 KB Output is correct
3 Correct 8 ms 8056 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 21820 KB Output is correct
2 Correct 23 ms 22356 KB Output is correct
3 Correct 22 ms 23364 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7380 KB Output is correct
2 Correct 10 ms 8404 KB Output is correct
3 Correct 42 ms 24500 KB Output is correct
4 Correct 11 ms 8504 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15704 KB Output is correct
2 Correct 36 ms 16936 KB Output is correct
3 Correct 29 ms 21384 KB Output is correct
4 Correct 24 ms 23188 KB Output is correct