제출 #312169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312169		Akashi	Islands (IOI08_islands)	C++14	18 / 100	922 ms	131076 KiB

islands

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

const int DIM = 1e6 + 5;

int n;
long long ans;
bool viz[DIM];
int tt[DIM], ct[DIM];
long long dp[DIM], sp[DIM], mx[DIM];

vector <pair <int, int>> v[DIM];

vector <pair <int, int>> cyc;
bool onCyc[DIM];

stack <pair <long long, int>> s1;
stack <pair <long long, int>> s2;

bool find_cycle(int nod) {
	viz[nod] = true;
	
	bool found = false;
	bool foundPapa = false;
	for (auto it : v[nod]) {
		if (it.x == tt[nod] && !foundPapa) {
			foundPapa = true;
			continue ;
		}

		if (!found && viz[it.x]) {
			int now = nod;
			
			while (now != tt[it.x]) {
				if (now != it.x) cyc.push_back({now, ct[now]});
				else cyc.push_back({now, it.y});
				onCyc[now] = true;
				now = tt[now];
			}
			found = true;
			continue ;
		}

		if (viz[it.x]) continue ;
		
		ct[it.x] = it.y; tt[it.x] = nod;
		bool ok = find_cycle(it.x);
		found |= ok;
	}

	return found;
}

void dfs(int nod, int papa = 0) {
	for (auto it : v[nod]) {
		if (onCyc[it.x] || it.x == papa) continue ;
		dfs(it.x, nod);
		ans = max(ans, dp[nod] + dp[it.x] + it.y);
		dp[nod] = max(dp[nod], dp[it.x] + it.y);
	}
}

int main() {
	scanf("%d", &n);
	int x, y;
	for (int i = 1; i <= n ; ++i) {
		scanf("%d%d", &x, &y);

		v[i].push_back({x, y});
		v[x].push_back({i, y});
	}

	long long sol = 0;
	for (int i = 1; i <= n ; ++i) {
		if (viz[i]) continue ;
		cyc.clear();
		ans = 0;
		find_cycle(i);

		long long sum = 0;
		for (auto elem : cyc) {
			int nod = elem.x;
			sp[nod] = sum;
			for (auto it : v[nod]) {
				if (!onCyc[it.x]) {
					dfs(it.x);
					ans = max(ans, mx[nod] + dp[it.x] + it.y);
					mx[nod] = max(mx[nod], dp[it.x] + it.y);
				}
			}

			while (!s1.empty() && mx[nod] + sp[nod] > s1.top().x) s1.pop();
			s1.push({mx[nod] + sp[nod], nod});
			sum = sum + elem.y;
			ans = max(ans, mx[nod]);
		}

		for (auto elem : cyc) {
			int nod = elem.x;
			while (!s2.empty() && mx[nod] + sum - sp[nod] > s2.top().x) s2.pop();
			s2.push({mx[nod] + sum - sp[nod], nod});
		}

		for (auto elem : cyc) {
			int nod = elem.x;
			if (!s1.empty() && s1.top().y == nod) s1.pop();
			if (!s2.empty() && s2.top().y == nod) s2.pop();
	
			if (s1.empty()) break ;
			ans = max(ans, mx[nod] - sp[nod] + s1.top().x);	
			ans = max(ans, mx[nod] + sp[nod] + s2.top().x);	
		}
		
		while (!s1.empty()) s1.pop();
		while (!s2.empty()) s2.pop();
		sol += ans;
	}

	printf("%lld\n", sol);

	return 0;
}

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

islands.cpp: In function 'int main()':
islands.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
islands.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 18 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10