oj.uz

Submission #575154

# Submission time Handle Problem Language Result Execution time Memory
575154 2022-06-09T19:21:01 Z Antekb Training (IOI07_training) C++14
100 / 100
 54 ms 24636 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 opt[N][K][K];//?
int dp[N][1<<K];//used subtrees
int dp2[N][5*N];//vert, out edg
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];
			if(v==1 && e==7){
				//cout<<id[u]<<" "<<id[w]<<"\n";
				//cout<<dp2[u][e]<<" "<<dp2[w][e]<<"\n";
				//cout<<edg2[7].nd.st<<" "<<edg2[7].nd.nd<<"\n";
			}
			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){
				if(v==2 && e==7){
					//cout<<"a";
					//cout<<dp2[edg2[e].nd.st][e]<<" "<<dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]<<" ";
				}
				dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]+dp2[edg2[e].nd.st][e];
				if(v==2 && e==7){
					//cout<<dp2[v][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);
	/*for(int i=1; i<=n; i++){
		cout<<i<<" "<<E[i].size()<<"\n";
		for(int j=0; j<(1<<E[i].size()); j++)cout<<dp[i][j]<<" ";
		cout<<"\n";
		for(int j=0; j<edg.size(); j++)cout<<dp2[i][j]<<" ";
			cout<<"\n";
	}*/
	cout<<sum-dp2[1][0];
}

Compilation message

training.cpp: In function 'void dfs(int, int)':
training.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<E[v].size(); i++)if(E[v][i]==p)swap(E[v][i], E[v].back());
      |               ~^~~~~~~~~~~~
training.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~
training.cpp: In function 'void dfs2(int)':
training.cpp:62:24: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   62 |   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 0 ms 468 KB Output is correct
2 Correct 0 ms 468 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 22 ms 20488 KB Output is correct
2 Correct 18 ms 20588 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 616 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 1176 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 7 ms 8376 KB Output is correct
2 Correct 8 ms 8304 KB Output is correct
3 Correct 9 ms 8020 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21812 KB Output is correct
2 Correct 24 ms 22408 KB Output is correct
3 Correct 23 ms 23244 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7432 KB Output is correct
2 Correct 10 ms 8384 KB Output is correct
3 Correct 54 ms 24636 KB Output is correct
4 Correct 11 ms 8532 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15724 KB Output is correct
2 Correct 41 ms 16960 KB Output is correct
3 Correct 28 ms 21460 KB Output is correct
4 Correct 35 ms 23200 KB Output is correct