Submission #1027049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027049		flappybird	Telegraph (JOI16_telegraph)	C++17	100 / 100	38 ms	41112 KiB

telegraph

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXQ 101010
#define INF 1'000'000'100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
int vis[MAX];
int A[MAX], C[MAX];
ll dp[2][MAX];
vector<int> adj[MAX];
int chk[MAX];
void dfs(int x) {
	vis[x] = 1;
	int mx = 0;
	for (auto v : adj[x]) if (!chk[v]) {
		dfs(v);
		dp[0][x] += dp[1][v];
		mx = max(mx, C[v]);
	}
	dp[1][x] = dp[0][x] + mx;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	ll sum = 0;
	for (i = 1; i <= N; i++) {
		cin >> A[i] >> C[i];
		sum += C[i];
		adj[A[i]].push_back(i);
	}
	vector<int> cyc;
	ll ans = 0;
	for (i = 1; i <= N; i++) if (!vis[i]) {
		cyc.clear();
		int v = i;
		while (1) {
			cyc.push_back(v);
			vis[v] = 1;
			v = A[v];
			if (vis[v]) {
				vector<int> cv;
				int chk = 0;
				for (auto x : cyc) {
					if (x == v) chk = 1;
					if (chk) cv.push_back(x);
				}
				cyc = cv;
				break;
			}
		}
		if (cyc.size() == N) {
			cout << 0;
			return 0;
		}
		for (auto x : cyc) chk[x] = 1;
		for (auto x : cyc) dfs(x);
		ll mn = 1e18;
		for (auto x : cyc) {
			int n = A[x];
			ll a, b;
			a = dp[0][n] + C[x];
			b = dp[1][n];
			ll m = max(a, b);
			mn = min(mn, m - b);
			ans += m;
		}
		ans -= mn;
	}
	cout << sum - ans;
}

Compilation message (stderr)

telegraph.cpp: In function 'int main()':
telegraph.cpp:65:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |   if (cyc.size() == N) {
      |       ~~~~~~~~~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30