Submission #120684

#	Time	Username	Problem	Language	Result	Execution time	Memory
120684		baluteshih	Training (IOI07_training)	C++14	17 / 100	62 ms	588 KiB

training

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<ll> G[1005];
int dfn[1005],out[1005],dft,dp[5005],pa[1005],seq[2050],xsum[2050],xr[1005];

struct mode
{
	int u,v,w;
	bool operator<(const mode &a)const{
		return dfn[v]<dfn[a.v];
	}
};

vector<mode> edge;

void dfs(int u,int f)
{
	dfn[u]=++dft,seq[dft]=u,pa[u]=f;
	for(int i:G[u])
		if(i!=f)
			dfs(i,u);
	out[u]=++dft,seq[dft]=u;
}

bool ancestor(int u,int v)
{
	return dfn[u]<=dfn[v]&&out[u]>=out[v];
}

int get_xor(int u,int v)
{
	if(ancestor(u,v))
		return xsum[dfn[v]]^xsum[dfn[u]];
	if(ancestor(v,u))
		return xsum[dfn[u]]^xsum[dfn[v]];
	if(out[u]<dfn[v])
		return xsum[dfn[v]]^xsum[out[u]-1];
	return xsum[dfn[u]]^xsum[out[v]-1];
}
 
int main()
{jizz
	srand(time(NULL));
	int n,m,u,v,w,cnt,ans=0,sum=0;
	cin >> n >> m;
	while(m--)
		if(cin >> u >> v >> w,w)
			edge.pb(mode{u,v,w});
		else
			G[u].pb(v),G[v].pb(u);
	dfs(1,1);
	for(auto &i:edge)
		if(dfn[i.u]>dfn[i.v]) swap(i.u,i.v);
	sort(ALL(edge));
	for(int i=0;i<edge.size();++i)
	{
		MEM(xr,0),MEM(xsum,0),cnt=0;
		for(int j=edge[i].u;!ancestor(j,edge[i].v);j=pa[j])
			xr[j]=rand(),++cnt;
		for(int j=edge[i].v;!ancestor(j,edge[i].u);j=pa[j])
			xr[j]=rand(),++cnt;
		for(int j=1;j<=dft;++j)
			xsum[j]=xsum[j-1]^xr[seq[j]];
		if(cnt&1) ans+=edge[i].w,dp[i]=-1;
		else
		{
			for(int j=0;j<i;++j)
				if(get_xor(edge[j].u,edge[j].v)==0)
					dp[i]=max(dp[j],dp[i]);
			dp[i]+=edge[i].w,sum+=edge[i].w;
		}
	}
	cout << ans+sum-*max_element(dp,dp+edge.size()) << "\n";
}

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<edge.size();++i)
              ~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 7 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9