Submission #626975

#	Time	Username	Problem	Language	Result	Execution time	Memory
626975		iomoon191	Telegraph (JOI16_telegraph)	C++17	100 / 100	67 ms	14716 KiB

telegraph

#ifndef TEST
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#endif
#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;
namespace fastIO {
	template <class T>
	inline void read(T &x){
		x = 0;
		bool fu = 0; char ch = 0;
		while(ch > '9' or ch < '0'){
			ch = getchar(); if(ch == '-') fu = 1;
		}
		while(ch <= '9' and ch >= '0'){
			x = (x * 10 - 48 + ch), ch = getchar();
		}
		if(fu) x = -x;
	}
	inline int read(){
		int x = 0;
		bool fu = 0; char ch = 0;
		while(ch >'9' or ch < '0'){
			ch = getchar(); if(ch == '-') fu = 1;
		}
		while(ch <= '9' and ch >= '0'){
			x = (x * 10 - 48 + ch), ch = getchar();
		}
		return fu ? -x : x;
	}
	template <class T, class... Args>
	inline void read(T& t, Args&... args){
		read(t); read(args...);
	}
	char _n_u_m_[40];
	template <class T>
	inline void write(T x){
		if(!x){ putchar('0'); return; }
		T tmp = x > 0 ? x : -x;
		if( x < 0 ) putchar('-');
		register int cnt = 0;
		while(tmp) {
			_n_u_m_[ cnt ++ ] = tmp % 10 + '0'; tmp /= 10;
		}
		while(cnt) putchar(_n_u_m_[ -- cnt ]) ;
	}
	template <class T>
	inline void write(T x , char ch) {
		write(x); putchar(ch);
	}
}
using namespace fastIO;
#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif
template <class T>
istream& operator >> (istream& in, vector<T> &x){
	for (auto &i : x) in >> i;
	return in;
}
template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	For(i, 0, sz(x) - 1){ 
		out << (i ? ", " : "") << x[i]; 
	}
	out << "]"; 
	return out;
}
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x){ 
	out << "(" << x.fi << ", " << x.se << ")"; 
	return out; 
}
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(){
#ifdef LOCAL
	using namespace chrono;
	auto start = high_resolution_clock::now();
#endif
	// freopen("cf.inp", "r", stdin);
	// freopen("cf.out", "w", stdout);
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int T = 1;
	while(T--) rmain();
#ifdef LOCAL
	auto end = high_resolution_clock::now();
	auto dur = duration_cast <milliseconds> (end - start).count();
	cout << "\n[" << dur << "ms]\n";
#endif
	return 0;
}

Compilation message (stderr)

telegraph.cpp: In function 'void fastIO::write(T)':
telegraph.cpp:61:16: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   61 |   register int cnt = 0;
      |                ^~~

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