Submission #626976

#	Time	Username	Problem	Language	Result	Execution time	Memory
626976		iomoon191	Telegraph (JOI16_telegraph)	C++17	100 / 100	76 ms	15132 KiB

telegraph

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define roF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define sz(a) (int) (a).size()
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
using namespace std;
using vi = vector<int>;
using ll = long long;
using pi = pair<int, int>;
// #define int ll;
mt19937 rng(random_device {}()); 
int rand(int a){
	return rng() % a;
}
const int N = 100005;
const int inf = 0x3f3f3f3f;

struct edge{
	ll x, c;
	edge(){}
	edge(ll x, ll c) : x(x), c(c){}
	bool operator < (const edge &e) const{
		return c > e.c;
	}
};

int n, a[N]; 
ll sum, c[N];
vector<edge> e[N];
bool vis[N], siv[N], cyc[N];
vi comp;

void fdfs(int x){
	if(x < 1 or vis[x]) return;
	comp.pb(x); vis[x] = 1;
	for(auto &i : e[x]) fdfs(i.x);
	fdfs(a[x]);
}

void rmain(){
	cin >> n;
	For(i, 1, n){
		cin >> a[i] >> c[i]; 
		sum += c[i];
		e[a[i]].pb(edge(i, c[i]));
		e[i].pb(edge(-1, 0));
	}
	For(i, 1, n) sort(all(e[i]));
	For(i, 1, n){
		if(vis[i]) continue;
		comp.clear(); fdfs(i);
		vi cycle; 
		int z = i;
		while(!siv[z]){
			siv[z] = 1;
			cycle.pb(z);
			z = a[z];
		}
		cycle.erase(cycle.begin(), find(all(cycle), z));
		for(auto &c : cycle) cyc[c] = 1;
		if(sz(cycle) == n){
			cout << "0"; return;
		}
		ll res = 0, ser = 0;
		for(auto &cc : comp) res += e[cc][0].c;
		for(auto &x : cycle){
			ser = max(ser, res - e[x][0].c + (cyc[e[x][0].x] ? e[x][1].c : e[x][0].c));
		}
		sum -= ser;
	}
	cout << sum;
}

signed main(int argc, char *argv[]){
	iostream::sync_with_stdio(0);
	int T = 1; 
	while(T--) rmain();
	return 0;
}

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