Submission #942484

#	Time	Username	Problem	Language	Result	Execution time	Memory
942484		MilosMilutinovic	Telegraph (JOI16_telegraph)	C++14	100 / 100	52 ms	10064 KiB

telegraph

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n;
int a[100005],c[100005],deg[100005];
vector<int> g[100005],topo;
bool ok[100005],take[100005];

bool check(){
	set<int> st;
	int x=1,lst=1;
	while(st.find(x)==st.end()){
		st.insert(x);
		lst=x;
		x=a[x];
	}
	return (int)st.size()==n&&a[lst]==1;
}

int main(){
	n=readint();
	for(int i=1;i<=n;i++) a[i]=readint(),c[i]=readint();
	if(check()){
		printf("0\n");
		return 0;
	}
	for(int i=1;i<=n;i++) g[a[i]].pb(i);
	for(int i=1;i<=n;i++) deg[a[i]]++;
	for(int i=1;i<=n;i++) if(deg[i]==0) topo.pb(i);
	for(int i=0;i<(int)topo.size();i++){
		int v=topo[i];
		deg[a[v]]--;
		if(deg[a[v]]==0) topo.pb(a[v]);
	}
	for(int i=1;i<=n;i++) ok[i]=true;
	for(int i:topo) ok[i]=false;
	ll s=0;
	for(int i=1;i<=n;i++){
		if(g[i].empty()) continue;
		sort(g[i].begin(),g[i].end(),[&](int x,int y){return c[x]>c[y];});
		s+=c[g[i][0]];
		take[g[i][0]]=true;
	}
	for(int i=1;i<=n;i++){
		if(!ok[i]) continue;
		int ver=i;
		vector<int> vec;
		while(ok[ver]){
			vec.pb(ver);
			ok[ver]=false;
			ver=a[ver];
		}
		bool all=true;
		for(int v:vec) all=(all&take[v]);
		if(all){
			int mx=-1e9;
			for(int v:vec){
				mx=max(mx,-c[g[v][0]]);
				if((int)g[v].size()>1) mx=max(mx,-c[g[v][0]]+c[g[v][1]]);
			}
			s+=mx;
		}
	}
	ll ans=-s;
	for(int i=1;i<=n;i++) ans+=c[i];
	printf("%lld\n",ans);
}

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