oj.uz

답안 #148121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148121 2019-08-31T14:03:54 Z WhipppedCream Islands (IOI08_islands) C++17
26 / 100
 562 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector< ii > vii;
typedef long long LL;
const int maxn = 1e6+5;
vii adj[maxn];
bool vis[maxn];
bool incycle[maxn];
bool spec[maxn];
int sz[maxn];
LL dp[maxn];
vi cycle;
int mark[maxn];
int Pair[maxn];
LL bestlen[maxn];
LL ndbest[maxn];
vector< LL > len;
int cnt(int u)
{
	if(vis[u]) return 0;
	vis[u] = 1;
	int res = 0;
	for(int i = 0; i< (int) adj[u].size(); i++)
	{
		int v = adj[u][i].X;
		res += cnt(v);
	}
	return res+1;
}
int find(int u, int p)
{
	if(vis[u]) return u;
	vis[u] = 1;
	int fak = -1;
	for(int i = 0; i< (int) adj[u].size(); i++)
	{
		int v = adj[u][i].X, w = adj[u][i].Y;
		if(v == p) continue;
		int k = find(v, u);
		if(k != -1) fak = k;
		if(k != -1)
		{
			incycle[u] = 1;
			cycle.pb(u);
			len.pb(w);
		}
	}
	if(fak == u) return -1;
	return fak;
}
LL val(int u, int p)
{
	if(incycle[u] && p) return -4e18;
	if(dp[u] != -1) return dp[u];
	dp[u] = 0;
	for(int i = 0; i< (int) adj[u].size(); i++)
	{
		int v = adj[u][i].X, w = adj[u][i].Y;
		if(v == p) continue;
		dp[u] = max(dp[u], w+val(v, u));
	}
	return dp[u];
}
LL findNDbest(int u, int p)
{
	if(incycle[u] && p) return -4e18;
	if(ndbest[u] != -1) return ndbest[u];
	LL best, ndbesT;
	best = ndbesT = 0;
	for(int i = 0; i< (int) adj[u].size(); i++)
	{
		int v = adj[u][i].X, w = adj[u][i].Y;
		if(v == p) continue;
		LL here = w+val(v, u);
		if(here> best)
		{
			ndbesT = best;
			best = here;
		}
		else if(here> ndbesT)
		{
			ndbesT = here;
		}
	}
	return ndbest[u] = ndbesT;
}
map<pair<int,int>, LL> lens;
int main()
{
	memset(dp, -1, sizeof dp);
	memset(ndbest, -1, sizeof ndbest);
	int n; scanf("%d", &n);
	for(int i = 1; i<= n; i++)
	{
		int u, w;
		scanf("%d %d", &u, &w);
		
		if(mark[i] == u)
		{
			spec[u] = spec[i] = 1;
			Pair[u] = i;
			Pair[i] = u;
		}
		adj[i].pb(ii(u, w));
		adj[u].pb(ii(i, w));
		mark[u] = i;
	}
	for(int i = 1; i<= n; i++)
	{
		if(vis[i]) continue;
		sz[i] = cnt(i);
	}		
	memset(vis, 0, sizeof vis);
	LL res = 0;
	for(int i = 1; i<= n; i++)
	{
		if(spec[i] && vis[i] == 0)
		{
			assert(0);
			cnt(i);
			incycle[i] = incycle[Pair[i]] = 1;
			//printf("%d %d\n", i, Pair[i]);
			//printf("---%lld\n", bestlen[Pair[i]]);
			//printf("%lld %lld\n", val(Pair[i], 0), findNDbest(Pair[i], 0));
			LL lens = 0;
			for(int j = 0; j< (int) adj[i].size(); j++)
			{
				if(adj[i][j].X == Pair[i]) lens = max(lens, (LL)adj[i][j].Y);
			}
			res += max(val(i, 0)+val(Pair[i], 0)+lens, max(val(i, 0)+findNDbest(i, 0), val(Pair[i], 0)+findNDbest(Pair[i], 0)));
			//printf("%lld\n", res);
		}
	}
	for(int i = 1; i<= n; i++)
	{
		if(vis[i]) continue;
		cycle.clear(); len.clear();
		//printf("%d\n", i);
		find(i, 0);
		deque<pair<LL, int> > foo;
		LL run = 0;
		LL best = 0;
		cycle.pop_back(); len.pop_back();
		int maxlen = cycle.size();
		//for(int j = 0; j< (int) cycle.size(); j++) printf("%d ", cycle[j]);
		//printf("\n");
		//for(int j = 0; j< (int) len.size(); j++) printf("%lld ", len[j]);
		for(int j = 0; j< (int) cycle.size(); j++)
		{
			int u = cycle[j];
			LL ton = j?len[j]:0;
			run += ton;
			//printf("%d: %lld\n", u, val(u, 0));
			while(!foo.empty() && j-foo.front().Y>= maxlen) foo.pop_front();
			if(!foo.empty())best = max(best, val(u, 0)+run+foo.front().X);
			while(!foo.empty() && foo.back().X<= val(u, 0)-run) foo.pop_back();
			foo.push_back(mp(val(u, 0)-run, j));
			best = max(best, val(u, 0)+findNDbest(u, 0));
		}
		for(int j = maxlen; j< 2*maxlen; j++)
		{
			int u = cycle[j-maxlen];
			LL ton = len[j-maxlen];
			run += ton;
			while(!foo.empty() && j-foo.front().Y>= maxlen) foo.pop_front();
			if(!foo.empty())best = max(best, val(u, 0)+run+foo.front().X);
			while(!foo.empty() && foo.back().X<= val(u, 0)-run) foo.pop_back();
			foo.push_back(mp(val(u, 0)-run, j));
		}
		res += best;
		//printf("%lld\n", res);
	}
	printf("%lld\n", res);
	return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
islands.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &w);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 96 ms 81656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 39 ms 40440 KB Output isn't correct
3 Correct 39 ms 40480 KB Output is correct
4 Runtime error 95 ms 81656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 38 ms 40568 KB Output is correct
6 Runtime error 92 ms 81756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 95 ms 81772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 39 ms 40432 KB Output isn't correct
9 Runtime error 93 ms 81656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 93 ms 81756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 93 ms 81768 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 40560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 41564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 45348 KB Output is correct
2 Correct 91 ms 47808 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 53408 KB Output is correct
2 Correct 167 ms 59192 KB Output is correct
3 Incorrect 200 ms 70784 KB Output isn't correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 64044 KB Output is correct
2 Correct 325 ms 86032 KB Output is correct
3 Correct 363 ms 95464 KB Output is correct
4 Correct 445 ms 118536 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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