제출 #148121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148121		WhipppedCream	Islands (IOI08_islands)	C++17	26 / 100	562 ms	131076 KiB

islands

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10