oj.uz

Submission #211262

# Submission time Handle Problem Language Result Execution time Memory
211262 2020-03-19T19:46:53 Z Lawliet Magic Tree (CEOI19_magictree) C++14
6 / 100
 538 ms 184592 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int LOG = 20;
const int MAXK = 3010;
const int MAXN = 100010;
 
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 <= 3 ; 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 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 9 ms 5120 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 538 ms 184592 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 11 ms 8832 KB Output is correct
2 Correct 11 ms 8832 KB Output is correct
3 Correct 11 ms 8832 KB Output is correct
4 Runtime error 208 ms 54604 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 212 ms 53408 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 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 9 ms 5120 KB Output is correct
10 Runtime error 229 ms 54352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18912 KB Output is correct
2 Correct 67 ms 23544 KB Output is correct
3 Correct 69 ms 23672 KB Output is correct
4 Correct 75 ms 30328 KB Output is correct
5 Correct 37 ms 21616 KB Output is correct
6 Runtime error 62 ms 22356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 9 ms 5120 KB Output is correct
10 Correct 11 ms 8832 KB Output is correct
11 Correct 11 ms 8832 KB Output is correct
12 Correct 11 ms 8832 KB Output is correct
13 Runtime error 208 ms 54604 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 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 7 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 9 ms 5120 KB Output is correct
10 Runtime error 538 ms 184592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -