Submission #219241

#	Time	Username	Problem	Language	Result	Execution time	Memory
219241		Lawliet	Training (IOI07_training)	C++17	100 / 100	25 ms	8576 KiB

training

#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 (stderr)

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 / 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