oj.uz

Submission #121281

# Submission time Handle Problem Language Result Execution time Memory
121281 2019-06-26T09:38:02 Z TadijaSebez Training (IOI07_training) C++11
100 / 100
 20 ms 8448 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8192 KB Output is correct
2 Correct 13 ms 8064 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 512 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1664 KB Output is correct
2 Correct 5 ms 1532 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4036 KB Output is correct
2 Correct 11 ms 2180 KB Output is correct
3 Correct 7 ms 2864 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1280 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 20 ms 8448 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4096 KB Output is correct
2 Correct 19 ms 7956 KB Output is correct
3 Correct 11 ms 3172 KB Output is correct
4 Correct 10 ms 2688 KB Output is correct