oj.uz

Submission #598766

# Submission time Handle Problem Language Result Execution time Memory
598766 2022-07-19T01:57:48 Z Bobaa Training (IOI07_training) C++17
0 / 100
 300 ms 512 KB 
#include<bits/stdc++.h>
using namespace std;

#define st first
#define nd second

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, pair<int, int>>> edg, edg2;
vector<int> dob;

void dfs(int v, int p){
	pre[v]=wsk++;
	par[v]=p;
	d[v]=d[p]+1;
	int sz=E[v].size(); 
	for(int i=0; i<sz; 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<sz; 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(){
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	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 dfs2(int)':
training.cpp:53:24: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   53 |   if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
      |      ~~~~~~~~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -