Submission #121021

#	Time	Username	Problem	Language	Result	Execution time	Memory
121021		tinder	Telegraph (JOI16_telegraph)	C++14	100 / 100	145 ms	16376 KiB

telegraph

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

const int maxn = 1e5 + 5;
using ll = long long;

int n;
ll c[maxn];
int a[maxn];
vector<int> g[maxn];
ll tot = 0;
vector<vector<int>> cycs;
int onstk[maxn];
int vis[maxn];
ll mx1[maxn], mx2[maxn];

void insert(int i, ll val) {
	mx2[i] = max(mx2[i], val);
	if(mx2[i] > mx1[i]) swap(mx1[i], mx2[i]);
}

int dfs(int u) {
	onstk[u] = 1;
	vis[u] = 1;
	for(int v : g[u]) {
		if(onstk[v]) {
			cycs.back().push_back(u);
			return 1;
		} else if(!vis[v]) {
			int ret = dfs(v);
			if(ret) return cycs.back().emplace_back(u), 1;
		}
	}
	onstk[u] = 0;
	return 0;
}

ll solve(vector<int> cyc) {
	ll offset = -1e18;
	for(int u : cyc) {
		int v = a[u];
		offset = max(offset, -mx1[v] + (c[u] == mx1[v] ? mx2[v] : mx1[v]));
	} return offset;
}

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> c[i];
		g[a[i]].emplace_back(i);
		insert(a[i], c[i]);
		tot += c[i];
	}
	int cyc_found = 0;
	cycs.emplace_back(vector<int>());
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			cyc_found = dfs(i);
			if(cyc_found) cycs.emplace_back(std::vector<int>());
		}
	}
	/*for(vector<int> &cyc : cycs) {
		cout << "cycle = "; for(int u : cyc) cout << u << ' '; cout << endl;
	}
	for(int i = 1; i <= n; i++) cout << mx1[i] << ' '; cout << endl;
	for(int i = 1; i <= n; i++) cout << mx2[i] << ' '; cout << endl;*/
	ll ans;
	if(cycs[0].size() == n) ans = 0;
	else {
		ll subtot = 0;
		for(int i = 1; i <= n; i++) {
			subtot += mx1[i];
		}
		for(vector<int> &cyc : cycs) {
			if(cyc.size()) {
				subtot += solve(cyc);
				// cout << "solve = " << solve(cyc) << endl;
			}
		}
		ans = tot - subtot;
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

telegraph.cpp: In function 'int main(int, const char**)':
telegraph.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cycs[0].size() == n) ans = 0;
     ~~~~~~~~~~~~~~~^~~~

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