oj.uz

답안 #211263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211263 2020-03-19T19:47:34 Z Lawliet Magic Tree (CEOI19_magictree) C++14
6 / 100
 1187 ms 610052 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int lli;
 
const int LOG = 20;
const int MAXK = 6010;
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

# 결과 실행 시간 메모리 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 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1187 ms 610052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 8832 KB Output is correct
2 Correct 12 ms 8832 KB Output is correct
3 Correct 11 ms 8832 KB Output is correct
4 Runtime error 224 ms 56668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 307 ms 79784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 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 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Runtime error 271 ms 80792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 19064 KB Output is correct
2 Correct 68 ms 23544 KB Output is correct
3 Correct 75 ms 23800 KB Output is correct
4 Correct 67 ms 30328 KB Output is correct
5 Correct 38 ms 21616 KB Output is correct
6 Runtime error 71 ms 22392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 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 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 13 ms 8832 KB Output is correct
11 Correct 12 ms 8832 KB Output is correct
12 Correct 11 ms 8832 KB Output is correct
13 Runtime error 224 ms 56668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 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 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Runtime error 1187 ms 610052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -