oj.uz

Submission #412432

# Submission time Handle Problem Language Result Execution time Memory
412432 2021-05-26T21:23:25 Z Jasiekstrz Training (IOI07_training) C++17
91 / 100
 300 ms 15260 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
const int K=10;
const int L=10;
vector<int> te[N+10];
vector<tuple<int,int,int,int>> edg_wait;
vector<pair<int,int>> edg[N+10];
vector<pair<int,int>> up[N+10];
int dep[N+10];
void dfs_dep(int x,int p)
{
	dep[x]=dep[p]+1;
	for(auto v:te[x])
	{
		if(v!=p)
			dfs_dep(v,x);
	}
	return;
}
int lsb(int x)
{
	x=(x&(-x));
	return __lg(x);
}
int dfs_ans(int x,int p)
{
	int ans=0;
	for(auto v:te[x])
	{
		if(v!=p)
			ans+=dfs_ans(v,x);
	}
	unordered_map<int,int> mp;
	int d[K][K];
	int du[K];
	int dp[(1<<K)];
	map<int,pair<int,int>> st;
	set<int> st2;
	for(int i=0;i<K;i++)
	{
		for(int j=0;j<K;j++)
			d[i][j]=0;
		du[i]=0;
	}
	for(auto v:te[x])
	{
		if(v!=p)
			mp[v]=mp.size();
	}
	for(auto v:te[x])
	{
		if(v==p)
			continue;
		for(auto [id,c]:up[v])
		{
			if(st.find(id)!=st.end())
			{
				d[mp[v]][st[id].fi]=d[st[id].fi][mp[v]]=max(d[st[id].fi][mp[v]],c+st[id].se);
				st2.insert(id);
			}
			st[id]={mp[v],c};
		}
	}
	for(auto [id,c]:edg[x])
	{
		if(st.find(id)!=st.end())
		{
			du[st[id].fi]=max(du[st[id].fi],c+st[id].se);
			st2.insert(id);
		}
	}
	dp[0]=0;
	for(int i=1;i<(1<<K);i++)
	{
		int v=lsb(i);
		dp[i]=dp[i^(1<<v)]+du[v];
		for(int j=0;j<K;j++)
		{
			if(i&(1<<j))
				dp[i]=max(dp[i],dp[i^(1<<v)^(1<<j)]+d[v][j]);
		}
	}
	for(auto v:te[x])
	{
		if(v==p)
			continue;
		for(auto [id,c]:up[v])
		{
			if(st2.find(id)==st2.end())
				up[x].emplace_back(id,c+dp[(1<<K)-1-(1<<mp[v])]-dp[(1<<K)-1]);
		}
	}
	for(auto [id,c]:edg[x])
	{
		if(st2.find(id)==st2.end())
			up[x].emplace_back(id,c);
	}
	//cerr<<x<<" "<<ans<<" "<<dp[(1<<K)-1]<<"\n";
	return ans+dp[(1<<K)-1];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(c==0)
		{
			te[a].push_back(b);
			te[b].push_back(a);
		}
		else
			edg_wait.emplace_back(a,b,c,i);
	}
	dfs_dep(1,0);
	for(auto [a,b,c,i]:edg_wait)
	{
		if(dep[a]%2==dep[b]%2)
		{
			edg[a].emplace_back(i,c);
			edg[b].emplace_back(i,c);
		}
		ans+=c;
	}
	cout<<ans-dfs_ans(1,0)/2<<"\n";
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 6948 KB Output is correct
2 Correct 119 ms 9412 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 5 ms 480 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 624 KB Output is correct
2 Correct 14 ms 488 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 744 KB Output is correct
2 Correct 26 ms 800 KB Output is correct
3 Correct 38 ms 1452 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1600 KB Output is correct
2 Correct 50 ms 1036 KB Output is correct
3 Correct 51 ms 1240 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 844 KB Output is correct
2 Correct 52 ms 2132 KB Output is correct
3 Correct 267 ms 13916 KB Output is correct
4 Correct 69 ms 3268 KB Output is correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 5444 KB Output is correct
2 Execution timed out 348 ms 15260 KB Time limit exceeded
3 Halted 0 ms 0 KB -