oj.uz

Submission #211261

# Submission time Handle Problem Language Result Execution time Memory
211261 2020-03-19T19:45:36 Z Lawliet Magic Tree (CEOI19_magictree) C++14
6 / 100
 1606 ms 184964 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] ];
}
 
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:181: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:185: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:192:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&node);
   ~~~~~^~~~~~~~~~~~
magictree.cpp:193: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 8 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 9 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1606 ms 184964 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 11264 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 209 ms 54736 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 213 ms 53532 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 8 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 9 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Runtime error 222 ms 54536 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 318 ms 35808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

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