Submission #412432

#	Time	Username	Problem	Language	Result	Execution time	Memory
412432		Jasiekstrz	Training (IOI07_training)	C++17	91 / 100	348 ms	15260 KiB

training

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 0 / 9