oj.uz

Submission #219241

# Submission time Handle Problem Language Result Execution time Memory
219241 2020-04-04T16:51:48 Z Lawliet Training (IOI07_training) C++17
100 / 100
 25 ms 8576 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int EXP = 1034;
const int MAXN = 1010;
const int MAXM = 5010;

struct edge
{
	int U, V, W;

	edge(int u, int v, int w)
		: U(u), V(v), W(w) {}
};

int n, m;

int pai[MAXN];
int prof[MAXN];
int dp[MAXN][EXP];
int indAdj[MAXN][MAXN];

vector< int > adj[MAXN];

vector< edge > edges;

vector< edge > root[MAXN];

void DFSInit(int cur, int p)
{
	pai[cur] = p;
	prof[cur] = prof[p] + 1;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz != p )
			DFSInit( viz , cur );
	}
}

int LCA(int U, int V)
{
	if( prof[U] < prof[V] ) swap( U , V );

	while( prof[U] != prof[V] )
		U = pai[U];

	while( U != V )
	{
		U = pai[U];
		V = pai[V];
	}

	return U;
}

bool isActive(int mask, int k) { return mask & (1 << k); }

int calculateIndAdj(int i, int j)
{
	int& ind = indAdj[i][j];

	if( ind != -1 ) return ind;
	return ind = calculateIndAdj( i , pai[j] );
}

int sumPath(int cur, int U)
{
	int sum = 0;
	int blocked = 0;

	while( cur != U )
	{
		sum += dp[U][blocked];

		blocked = (1 << calculateIndAdj( pai[U] , U ));
		U = pai[U];
	}

	return sum;
}

void DFSCalculate(int cur)
{
	int sz = adj[cur].size();

	for(int i = 0 ; i < sz ; i++)
		DFSCalculate( adj[cur][i] );

	vector< int > sumTransition;
	vector< int > blockTransition;

	int all = (1 << sz) - 1;

	for(int mask = (1 << sz) - 2 ; mask >= 0 ; mask--)
	{
		int op = all^mask;

		int b = op & -op;
		int viz = adj[cur][ log2(b) ];

		dp[cur][mask] = dp[cur][mask + b] + dp[viz][0];
	}

	for(int i = 0 ; i < root[cur].size() ; i++)
	{
		int U = root[cur][i].U;
		int V = root[cur][i].V;
		int W = root[cur][i].W;

		int curSum = W;
		curSum += sumPath( cur , U );
		curSum += sumPath( cur , V );

		int blocked = (1 << calculateIndAdj( cur , V ));
		if( U != cur ) blocked += (1 << calculateIndAdj( cur , U ));

		for(int mask = 0 ; mask < (1 << sz) ; mask++)
		{
			if( (mask & blocked) != 0 ) continue;

			int curAnswer = dp[cur][ mask | blocked ];
			curAnswer += curSum;

			dp[cur][mask] = max( dp[cur][mask] , curAnswer );
		}
	}
}

int main()
{
	scanf("%d %d",&n,&m);

	memset( indAdj , -1 , sizeof(indAdj) );

	int sum = 0;

	for(int 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 edges.push_back( edge( U , V , W ) );

		sum += W;
	}

	DFSInit( 1 , 0 );

	for(int i = 1 ; i <= n ; i++)
	{
		int sz = adj[i].size();

		for(int j = 0 ; j < sz ; j++)
			if( adj[i][j] == pai[i] ) swap( adj[i][j] , adj[i][sz - 1] );

		if( i != 1 ) adj[i].pop_back();

		sort( adj[i].begin() , adj[i].end() );

		for(int j = 0 ; j < adj[i].size() ; j++)
			indAdj[i][ adj[i][j] ] = j;
	}

	for(int i = 0 ; i < edges.size() ; i++)
	{
		int& U = edges[i].U;
		int& V = edges[i].V;
		int W = edges[i].W;
		int L = LCA( U , V );

		if( prof[U] > prof[V] ) swap( U , V );

		int dist = prof[U] + prof[V];
		dist -= 2*prof[L];

		if( dist%2 == 1 ) continue;

		root[L].push_back( edges[i] );
	}

	DFSCalculate( 1 );

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

Compilation message

training.cpp: In function 'void DFSInit(int, int)':
training.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
training.cpp: In function 'void DFSCalculate(int)':
training.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < root[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < adj[i].size() ; j++)
                   ~~^~~~~~~~~~~~~~~
training.cpp:174:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < edges.size() ; i++)
                  ~~^~~~~~~~~~~~~~
training.cpp:178:7: warning: unused variable 'W' [-Wunused-variable]
   int W = edges[i].W;
       ^
training.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
training.cpp:145:8: 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 7 ms 4480 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8576 KB Output is correct
2 Correct 19 ms 8576 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 7 ms 4480 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 7 ms 4608 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4840 KB Output is correct
2 Correct 9 ms 4736 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4992 KB Output is correct
2 Correct 9 ms 4992 KB Output is correct
3 Correct 11 ms 5632 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6144 KB Output is correct
2 Correct 11 ms 5248 KB Output is correct
3 Correct 10 ms 5504 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4736 KB Output is correct
2 Correct 9 ms 5632 KB Output is correct
3 Correct 25 ms 8552 KB Output is correct
4 Correct 10 ms 5760 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6144 KB Output is correct
2 Correct 23 ms 8576 KB Output is correct
3 Correct 13 ms 5632 KB Output is correct
4 Correct 12 ms 5376 KB Output is correct