oj.uz

Submission #100892

# Submission time Handle Problem Language Result Execution time Memory
100892 2019-03-15T03:40:04 Z autumn_eel Telegraph (JOI16_telegraph) C++14
0 / 100
 20 ms 16256 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define int long long

vector<int>E[200000],G[200000];
int deg[200000];
int a[200000],c[200000];
bool loop[200000];
int id[200000];

ll loopcnt[200000];
vector<int>loopvs[200000];

void dfs(int v,int k){
	id[v]=k;
	for(int u:E[v]){
		if(id[u]==-1){
			dfs(u,k);
		}
	}
}
ll ans=0;

void dfs2(int v){
	int Max=0;
	for(int u:E[v]){
		if(loop[u])continue;
		dfs2(u);
		Max=max(Max,c[u]);
	}
	if(!loop[v])ans+=Max;
}


signed main(){
	int n;cin>>n;
	rep(i,n){
		scanf("%lld%lld",&a[i],&c[i]);a[i]--;
		deg[a[i]]++;deg[i]++;
		E[a[i]].push_back(i);
		G[a[i]].push_back(i);
		G[i].push_back(a[i]);
	}
	queue<int>que;
	rep(i,n){
		if(deg[i]==1){
			que.push(i);
		}
	}
	memset(loop,1,sizeof(loop));
	while(!que.empty()){
		int p=que.front();que.pop();
		loop[p]=false;
		for(int u:G[p]){
			if(deg[u]>1){
				deg[u]--;
				if(deg[u]==1){
					que.push(u);
				}
			}
		}
	}
	memset(id,-1,sizeof(id));
	int cnt=0;
	rep(i,n){
		if(loop[i]&&id[i]==-1){
			dfs(i,cnt++);
		}
	}
	bool ok=true;
	rep(i,n){
		if(!loop[i])ok=false;
	}
	if(ok&&cnt==1){
		puts("0");
		return 0;
	}
	rep(i,n){
		if(loop[i]){
			dfs2(i);
			loopcnt[id[i]]+=c[i];
			loopvs[id[i]].push_back(i);
		}
	}
	rep(i,cnt){
		if(loopvs[i].empty())continue;
		int Max=INT_MIN;
		for(int v:loopvs[i]){
			int C=0,D=0;
			for(int u:E[v]){
				if(loop[u])C=c[u];
				else D=max(D,c[u]);
			}
			Max=max(Max,D-C);
		}
		ans+=loopcnt[i]+Max;
	}
	ll ans2=0;
	rep(i,n)ans2+=c[i];
	cout<<ans2-ans<<endl;
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i],&c[i]);a[i]--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16128 KB Output is correct
2 Correct 17 ms 16128 KB Output is correct
3 Correct 17 ms 16128 KB Output is correct
4 Correct 20 ms 16256 KB Output is correct
5 Incorrect 12 ms 16256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16128 KB Output is correct
2 Correct 17 ms 16128 KB Output is correct
3 Correct 17 ms 16128 KB Output is correct
4 Correct 20 ms 16256 KB Output is correct
5 Incorrect 12 ms 16256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16128 KB Output is correct
2 Correct 17 ms 16128 KB Output is correct
3 Correct 17 ms 16128 KB Output is correct
4 Correct 20 ms 16256 KB Output is correct
5 Incorrect 12 ms 16256 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16128 KB Output is correct
2 Correct 17 ms 16128 KB Output is correct
3 Correct 17 ms 16128 KB Output is correct
4 Correct 20 ms 16256 KB Output is correct
5 Incorrect 12 ms 16256 KB Output isn't correct
6 Halted 0 ms 0 KB -