oj.uz

Submission #197542

# Submission time Handle Problem Language Result Execution time Memory
197542 2020-01-21T15:46:59 Z arnold518 Training (IOI07_training) C++14
100 / 100
 27 ms 4728 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;

struct Edge { int u, v, w; };

int N, M, num[MAXN+10];
vector<int> adj[MAXN+10], chd[MAXN+10];
vector<Edge> E, edge[MAXN+10];

int dep[MAXN+10], par[MAXN+10][20], sum;

void dfs(int now, int bef, int depth)
{
    int i, j;
	dep[now]=depth;
	par[now][0]=bef;
	for(auto nxt : adj[now])
	{
		if(nxt==bef) continue;
		chd[now].push_back(nxt);
		dfs(nxt, now, depth+1);
	}
	for(i=0; i<chd[now].size(); i++) num[chd[now][i]]=i;
}

int lca(int u, int v)
{
	int i, j;
	if(dep[u]>dep[v]) swap(u, v);
	for(i=10; i>=0; i--) if(dep[u]<=dep[par[v][i]]) v=par[v][i];
	if(u==v) return u;
	for(i=10; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	return par[u][0];
}

int dist(int u, int v)
{
	int w=lca(u, v);
	return dep[u]+dep[v]-dep[w]-dep[w];
}

int dp[MAXN+10][(1<<10)+10];
void dfs2(int now)
{
	int i, j;
	for(auto nxt : chd[now]) dfs2(nxt);

	int sz=chd[now].size(), t;
	
	//printf("NOW %d\n", now);
	vector<int> val;
	for(auto &e : edge[now])
	{
		t=e.w;

		int u=e.u, v=e.u;
		while(u!=now)
		{
			if(u!=v) t+=dp[u][(1<<num[v])];
			else t+=dp[u][0];
			v=u; u=par[u][0];
		}
		e.u=v;

		u=e.v, v=e.v;
		while(u!=now)
		{
			if(u!=v) t+=dp[u][(1<<num[v])];
			else t+=dp[u][0];
			v=u; u=par[u][0];
		}
		e.v=v;

		val.push_back(t);
	}

	for(i=0; i<(1<<sz); i++)
	{
		for(j=0; j<sz; j++)
		{
			if(i&(1<<j)) continue;
			dp[now][i]+=dp[chd[now][j]][0];
		}
	}

	for(i=(1<<sz)-1; i>=0; i--)
	{
		for(j=0; j<edge[now].size(); j++)
		{
			if(edge[now][j].u!=now && i&(1<<num[edge[now][j].u])) continue;
			if(edge[now][j].v!=now && i&(1<<num[edge[now][j].v])) continue;

			int mask=i;
			if(edge[now][j].u!=now) mask|=(1<<num[edge[now][j].u]);
			if(edge[now][j].v!=now) mask|=(1<<num[edge[now][j].v]);
			dp[now][i]=max(dp[now][i], dp[now][mask]+val[j]);
		}
	}
}

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    for(i=1; i<=M; i++)
    {
    	int u, v, w;
    	scanf("%d%d%d", &u, &v, &w);
    	if(w==0) adj[u].push_back(v), adj[v].push_back(u);
    	else E.push_back({u, v, w});
    	sum+=w;
    }

    dfs(1, 1, 1);
    for(i=1; i<=10; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

    for(auto it : E) if(dist(it.u, it.v)%2==0) edge[lca(it.u, it.v)].push_back(it);

    dfs2(1);
	printf("%d", sum-dp[1][0]);
}

Compilation message

training.cpp: In function 'void dfs(int, int, int)':
training.cpp:29:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<chd[now].size(); i++) num[chd[now][i]]=i;
           ~^~~~~~~~~~~~~~~~
training.cpp:20:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
training.cpp: In function 'int lca(int, int)':
training.cpp:34:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
training.cpp: In function 'void dfs2(int)':
training.cpp:94:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<edge[now].size(); j++)
            ~^~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
training.cpp:115:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d%d", &u, &v, &w);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 11 ms 4728 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1060 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 16 ms 1656 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2172 KB Output is correct
2 Correct 15 ms 1272 KB Output is correct
3 Correct 7 ms 1528 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 5 ms 1656 KB Output is correct
3 Correct 27 ms 4600 KB Output is correct
4 Correct 7 ms 1788 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2168 KB Output is correct
2 Correct 21 ms 4600 KB Output is correct
3 Correct 5 ms 1656 KB Output is correct
4 Correct 14 ms 1528 KB Output is correct