oj.uz

Submission #211259

# Submission time Handle Problem Language Result Execution time Memory
211259 2020-03-19T19:40:05 Z Lawliet Magic Tree (CEOI19_magictree) C++14
6 / 100
 1586 ms 181476 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 );

		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;
}
 
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();
 
	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:162: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:166: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:173:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&node);
   ~~~~~^~~~~~~~~~~~
magictree.cpp:174: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 8 ms 5120 KB Output is correct
3 Correct 7 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 9 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1586 ms 181476 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 13 ms 11136 KB Output is correct
2 Correct 13 ms 11136 KB Output is correct
3 Correct 14 ms 11136 KB Output is correct
4 Runtime error 176 ms 45304 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 215 ms 55420 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 8 ms 5120 KB Output is correct
3 Correct 7 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 9 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Runtime error 205 ms 55708 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 Incorrect 316 ms 35708 KB Output isn't correct
2 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 8 ms 5120 KB Output is correct
3 Correct 7 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 9 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 13 ms 11136 KB Output is correct
11 Correct 13 ms 11136 KB Output is correct
12 Correct 14 ms 11136 KB Output is correct
13 Runtime error 176 ms 45304 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 8 ms 5120 KB Output is correct
3 Correct 7 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 9 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Runtime error 1586 ms 181476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -