oj.uz

Submission #412433

# Submission time Handle Problem Language Result Execution time Memory
412433 2021-05-26T21:27:07 Z Jasiekstrz Training (IOI07_training) C++17
91 / 100
 300 ms 15100 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];
int mp[N+10];
map<int,pair<int,int>> st;
set<int> st2;
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);
	}
	int d[K][K];
	int du[K];
	int dp[(1<<K)];
	st.clear();st2.clear();
	for(int i=0;i<K;i++)
	{
		for(int j=0;j<K;j++)
			d[i][j]=0;
		du[i]=0;
	}
	int nr=0;
	for(auto v:te[x])
	{
		if(v!=p)
			mp[v]=nr++;
	}
	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 vv:up[v])
		{
			if(st2.find(vv.fi)==st2.end())
				up[x].emplace_back(vv.fi,vv.se+dp[(1<<K)-1-(1<<mp[v])]-dp[(1<<K)-1]);
		}
	}
	for(auto v:edg[x])
	{
		if(st2.find(v.fi)==st2.end())
			up[x].emplace_back(v);
	}
	//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 1 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 3 ms 588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 6968 KB Output is correct
2 Correct 130 ms 9284 KB Output is correct

Subtask #4
7.0 / 7.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 #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 460 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 612 KB Output is correct
2 Correct 13 ms 500 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 768 KB Output is correct
2 Correct 28 ms 796 KB Output is correct
3 Correct 32 ms 1476 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1508 KB Output is correct
2 Correct 46 ms 1040 KB Output is correct
3 Correct 57 ms 1188 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 716 KB Output is correct
2 Correct 45 ms 2092 KB Output is correct
3 Correct 245 ms 13788 KB Output is correct
4 Correct 64 ms 3252 KB Output is correct

Subtask #11
0 / 9.0

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