oj.uz

Submission #120685

# Submission time Handle Problem Language Result Execution time Memory
120685 2019-06-25T08:17:35 Z baluteshih Training (IOI07_training) C++14
37 / 100
 67 ms 768 KB 
#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)||ancestor(v,u))
		return xsum[dfn[v]]^xsum[dfn[u]];
	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,root=1;
	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);
	for(int i=2;i<=n;++i)
		if(G[i].size()<G[root].size()) root=i;
	dfs(root,root);
	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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 8 ms 512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 512 KB Output is correct
2 Correct 24 ms 768 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -