oj.uz

Submission #211265

# Submission time Handle Problem Language Result Execution time Memory
211265 2020-03-19T19:49:47 Z Lawliet Magic Tree (CEOI19_magictree) C++14
19 / 100
 1229 ms 662936 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int LOG = 30;
const int MAXK = 6010;
const int MAXN = 200010;
 
int n, m, k;
int curTime;
int cntNode;
 
int t[MAXN];
int w[MAXN];
int tin[MAXN];
int tout[MAXN];
int prof[MAXN];
int tab[LOG][MAXN];

int auxT[MAXN];
int auxW[MAXN];

int inv[MAXN];
int compressed[MAXN];
 
lli dp[MAXK][MAXK];
 
vector< int > adj[MAXN];
vector< int > auxTree[MAXN];
 
void DFSCalculate(int cur)
{
	for(int i = 0 ; i < adj[cur].size() ; i++)
		DFSCalculate( adj[cur][i] );
 
	for(int j = 1 ; j <= k ; j++)
	{
		lli sum = 0;
		if( t[cur] == j ) sum = w[cur];
 
		for(int i = 0 ; i < adj[cur].size() ; i++)
			sum += dp[ adj[cur][i] ][j];
 
		dp[cur][j] = max( dp[cur][j - 1] , sum );
	}
}

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

	int d = prof[U] - prof[V];

	for(int k = 0 ; k < LOG ; k++)
		if( d & (1 << k) ) U = tab[k][U];

	if( U == V ) return U;

	for(int k = LOG - 1 ; k >= 0 ; k--)
	{
		if( tab[k][U] != tab[k][V] ) 
		{
			U = tab[k][U];
			V = tab[k][V];
		}
	}

	return tab[0][U];
}

void DFSInit(int cur, int d)
{
	prof[cur] = d;
	tin[cur] = ++curTime;

	for(int i = 0 ; i < auxTree[cur].size() ; i++)
		DFSInit( auxTree[cur][i] , d + 1 );

	tout[cur] = curTime;
}

bool cmp(int U, int V) { return tin[U] < tin[V]; }

int getNode(int U)
{
	if( compressed[U] == 0 )
	{
		compressed[U] = ++cntNode;
		inv[ cntNode ] = U;
	}

	return compressed[U];
}

void compressTree()
{
	for(int k = 1 ; k < LOG ; k++)
	{
		for(int i = 1 ; i <= n ; i++)
		{
			int jump = tab[k - 1][i];
			tab[k][i] = tab[k - 1][jump];
		}
	}

	DFSInit( 1 , 0 );

	vector< int > v;

	for(int i = 1 ; i <= n ; i++)
		if( auxW[i] != 0 ) v.push_back( i );

	v.push_back( 1 );

	sort( v.begin() , v.end() , cmp );

	int sz = v.size();

	for(int i = 0 ; i < sz - 1 ; i++)
		v.push_back( LCA( v[i] , v[i + 1] ) );

	sort( v.begin() , v.end() , cmp );

	vector< int > s;
	s.push_back( v[0] );

	for(int i = 1 ; i < v.size() ; i++)
	{
		if( v[i] == v[i - 1] ) continue;

		while( true )
		{
			int last = s.back();

			if( tin[last] <= tin[ v[i] ] && tout[ v[i] ] <= tout[last] ) break;

			s.pop_back();
		}

		int U = getNode( s.back() );
		int V = getNode( v[i] );

		adj[ U ].push_back( V );

		//printf("..... %d %d      %d %d\n",U,V,inv[U],inv[V]);

		s.push_back( v[i] );
	}

	for(int i = 1 ; i <= n ; i++)
	{
		if( compressed[i] == 0 ) continue;

		t[ compressed[i] ] = auxT[i];
		w[ compressed[i] ] = auxW[i];
	}

	n = cntNode;
}

void compressTime()
{
	set< int > s;
	map< int , int > conv;

	for(int i = 1 ; i <= n ; i++)
		s.insert( t[i] );

	int cnt = 0;

	for(auto it = s.begin() ; it != s.end() ; it++)
		conv[ *it ] = ++cnt;

	for(int i = 1 ; i <= n ; i++)
		t[i] = conv[ t[i] ];

	k = 0;

	for(int i = 1 ; i <= n ; i++)
		k = max( k , t[i] );
}
 
int main()
{
	scanf("%d %d %d",&n,&m,&k);
 
	for(int i = 2 ; i <= n ; i++)
	{
		scanf("%d",&tab[0][i]);
		auxTree[ tab[0][i] ].push_back( i );
	}
 
	for(int i = 1 ; i <= m ; i++)
	{
		int node;
		scanf("%d",&node);
		scanf("%d %d",&auxT[node],&auxW[node]);
	}

	compressTree();
	compressTime();
 
	DFSCalculate( 1 );
 
	printf("%lld\n",dp[1][k]);
}

Compilation message

magictree.cpp: In function 'void DFSCalculate(int)':
magictree.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
magictree.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[cur].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~
magictree.cpp: In function 'void DFSInit(int, int)':
magictree.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < auxTree[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~
magictree.cpp: In function 'void compressTree()':
magictree.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1 ; i < v.size() ; i++)
                  ~~^~~~~~~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
magictree.cpp:190:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&tab[0][i]);
   ~~~~~^~~~~~~~~~~~~~~~~
magictree.cpp:197:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&node);
   ~~~~~^~~~~~~~~~~~
magictree.cpp:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&auxT[node],&auxW[node]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 11 ms 9984 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 11 ms 9984 KB Output is correct
7 Correct 12 ms 9984 KB Output is correct
8 Correct 11 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1229 ms 662936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13696 KB Output is correct
2 Correct 15 ms 13824 KB Output is correct
3 Correct 14 ms 13824 KB Output is correct
4 Runtime error 257 ms 85052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 395 ms 109724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 11 ms 9984 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 11 ms 9984 KB Output is correct
7 Correct 12 ms 9984 KB Output is correct
8 Correct 11 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Runtime error 338 ms 111404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 25720 KB Output is correct
2 Correct 74 ms 38008 KB Output is correct
3 Correct 76 ms 38264 KB Output is correct
4 Correct 76 ms 44792 KB Output is correct
5 Correct 46 ms 36336 KB Output is correct
6 Correct 96 ms 45560 KB Output is correct
7 Correct 70 ms 43512 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 11 ms 9984 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 11 ms 9984 KB Output is correct
7 Correct 12 ms 9984 KB Output is correct
8 Correct 11 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Correct 21 ms 13696 KB Output is correct
11 Correct 15 ms 13824 KB Output is correct
12 Correct 14 ms 13824 KB Output is correct
13 Runtime error 257 ms 85052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 11 ms 9984 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 11 ms 9984 KB Output is correct
5 Correct 12 ms 9984 KB Output is correct
6 Correct 11 ms 9984 KB Output is correct
7 Correct 12 ms 9984 KB Output is correct
8 Correct 11 ms 9984 KB Output is correct
9 Correct 11 ms 9984 KB Output is correct
10 Runtime error 1229 ms 662936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -