oj.uz

Submission #104343

# Submission time Handle Problem Language Result Execution time Memory
104343 2019-04-05T12:17:46 Z DodgeBallMan Islands (IOI08_islands) C++14
100 / 100
 943 ms 76564 KB 
#include <bits/stdc++.h>
#define pll pair<long long, long long>
#define x first 
#define y second

using namespace std;

const int N = 1e6 + 100;
int n, deg[N];
long long dm[N], ans;
pll par[N], dp[N];
int main()
{
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i++ ) {
		long long p, w;
		scanf("%lld %lld",&p,&w);
		par[i] = pll( p, w );
		deg[p]++;
	}
	queue<int> q;
	for( int i = 1 ; i <= n ; i++ ) if( !deg[i] ) q.emplace( i );
	while( !q.empty() ) {
		int now = q.front();
		q.pop();
		dm[now] = max( dm[now], dp[now].x + dp[now].y );
		dm[par[now].x] = max( dp[par[now].x].x, dm[now] );
		long long path = dp[now].x + par[now].y;
		if( path > dp[par[now].x].x ) swap( path, dp[par[now].x].x );
		if( path > dp[par[now].x].y ) swap( path, dp[par[now].x].y );
		if( !--deg[par[now].x] ) q.emplace( par[now].x );
	}
	for( int i = 1 ; i <= n ; i++ ) if( deg[i] ) {
		int p = i;
		vector<pll> cyc;
		deque<pll> q;
		while( deg[p] ) {
			deg[p]--;
			cyc.emplace_back( pll( p, par[p].y ) );
			p = par[p].x;
		}
		long long ret = 0, dis = cyc[0].y, trash = 0;
		for( pll v : cyc ) ret = max( ret, max( dm[v.x], dp[v.x].x + dp[v.x].y ) );
		for( int i = 1 ; i < cyc.size() ; i++ ) {
			while( !q.empty() && q.back().x < dis + dp[cyc[i].x].x ) q.pop_back();
			q.emplace_back( pll( dis + dp[cyc[i].x].x, cyc[i].x ) );
			dis += cyc[i].y;
		}
		ret = max( ret, dp[cyc[0].x].x + q.front().x );
		for( int i = 0 ; i < cyc.size() - 1 ; i++ ) {
			if( q.front().y == cyc[i + 1].x ) q.pop_front();
			while( !q.empty() && q.back().x < dis + dp[cyc[i].x].x ) q.pop_back();
			q.emplace_back( pll( dis + dp[cyc[i].x].x, cyc[i].x ) );
			dis += cyc[i].y, trash += cyc[i].y;
			ret = max( ret, dp[cyc[i+1].x].x + q.front().x - trash );
		}
		ans += ret;
	}
	printf("%lld",ans);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for( int i = 1 ; i < cyc.size() ; i++ ) {
                    ~~^~~~~~~~~~~~
islands.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for( int i = 0 ; i < cyc.size() - 1 ; i++ ) {
                    ~~^~~~~~~~~~~~~~~~
islands.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
islands.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&p,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1324 KB Output is correct
2 Correct 18 ms 2696 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3828 KB Output is correct
2 Correct 43 ms 6084 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 12296 KB Output is correct
2 Correct 80 ms 12344 KB Output is correct
3 Correct 93 ms 19308 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 21716 KB Output is correct
2 Correct 212 ms 32704 KB Output is correct
3 Correct 148 ms 27852 KB Output is correct
4 Correct 233 ms 46444 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 43484 KB Output is correct
2 Correct 553 ms 59260 KB Output is correct
3 Correct 239 ms 45180 KB Output is correct
4 Correct 417 ms 65436 KB Output is correct
5 Correct 413 ms 65952 KB Output is correct
6 Correct 773 ms 58116 KB Output is correct
7 Correct 449 ms 76564 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 58716 KB Output is correct
2 Correct 297 ms 58872 KB Output is correct
3 Correct 412 ms 51928 KB Output is correct
4 Correct 481 ms 34976 KB Output is correct
5 Correct 383 ms 65904 KB Output is correct
6 Correct 406 ms 59096 KB Output is correct
7 Correct 943 ms 59000 KB Output is correct