Submission #121281

#	Time	Username	Problem	Language	Result	Execution time	Memory
121281		TadijaSebez	Training (IOI07_training)	C++11	100 / 100	20 ms	8448 KiB

training

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1050;
const int L=10;
const int K=10;
vector<int> E[N];
struct Edge{ int u,v,c;Edge(){}Edge(int a, int b, int d):u(a),v(b),c(d){}};
vector<Edge> es;
vector<Edge> cyc[N];
int dep[N],par[N][L],deg[N],dp[N][1<<K],idx[N][N],full[N];
void DFS(int u, int p)
{
	int cnt=0;
	dep[u]=dep[p]+1;
	par[u][0]=p;
	for(int i=1;i<L;i++) par[u][i]=par[par[u][i-1]][i-1];
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p)
		{
			idx[u][v]=cnt++;
			DFS(v,u);
		}
	}
	deg[u]=cnt;
	full[u]=(1<<cnt)-1;
}
int LCA(int u, int v)
{
	if(dep[u]<dep[v]) return LCA(v,u);
	for(int i=L-1;~i;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
	for(int i=L-1;~i;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}
void Solve(int u, int p)
{
	for(int v:E[u]) if(v!=p) Solve(v,u);
	vector<pair<int,int>> work;
	for(Edge e:cyc[u])
	{
		int x=e.u,y=e.v;
		int sum=e.c,last=0,mask=0;
		for(;x!=u;x=par[x][0])
		{
			if(last) sum+=dp[x][full[x]^(1<<idx[x][last])];
			else sum+=dp[x][full[x]];
			last=x;
		}
		if(last) mask^=1<<idx[u][last];
		last=0;
		for(;y!=u;y=par[y][0])
		{
			if(last) sum+=dp[y][full[y]^(1<<idx[y][last])];
			else sum+=dp[y][full[y]];
			last=y;
		}
		if(last) mask^=1<<idx[u][last];
		work.pb({mask,sum});
	}
	for(int v:E[u]) if(v!=p) work.pb({1<<idx[u][v],dp[v][full[v]]});
	for(int i=1;i<=full[u];i++)
	{
		for(auto w:work)
		{
			if((i&w.first)==w.first) dp[u][i]=max(dp[u][i],dp[u][i^w.first]+w.second);
		}
	}
}
int main()
{
	int n,m,u,v,c;
	scanf("%i %i",&n,&m);
	int sum=0;
	while(m--)
	{
		scanf("%i %i %i",&u,&v,&c);
		if(!c) E[u].pb(v),E[v].pb(u);
		else es.pb(Edge(u,v,c));
		sum+=c;
	}
	DFS(1,0);
	for(Edge e:es)
	{
		int lca=LCA(e.u,e.v);
		int dist=dep[e.u]+dep[e.v]-2*dep[lca];
		if(dist&1) continue;
		cyc[lca].pb(e);
	}
	Solve(1,0);
	printf("%i\n",sum-dp[1][full[1]]);
	return 0;
}

Compilation message (stderr)

training.cpp: In function 'void DFS(int, int)':
training.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
training.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&u,&v,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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: 9 / 9