Submission #55881

#	Time	Username	Problem	Language	Result	Execution time	Memory
55881		khsoo01	Telegraph (JOI16_telegraph)	C++11	100 / 100	125 ms	8664 KiB

telegraph

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll N = 100005, inf = 1e18;

ll n, d[N], v[N], ind[N], dt[N], ans;
bool vis[N];

vector<pll> adj[N];
queue<ll> q;

ll solve (ll I) {
	ll A, B, C = 0, R = 0;
	for(auto &T : adj[I]) {
		tie(A, B) = T;
		R += solve(A) + B;
		C = max(B, C);
	}
	return R - C;
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&d[i],&v[i]);
		adj[d[i]].push_back({i, v[i]});
		ind[d[i]]++;
	}
	for(ll i=1;i<=n;i++) {
		if(ind[i] == 0) q.push(i);
	}
	while(!q.empty()) {
		ll C = q.front();
		q.pop();
		if(--ind[d[C]] == 0) q.push(d[C]);
	}
	for(ll i=1;i<=n;i++) {
		if(vis[i] || !ind[i]) continue;
		ll O = inf, F = 0, C = 0;
		for(ll j=i;!vis[j];j=d[j]) {
			vis[j] = true;
			C++;
			ll X, Y = 0, A, B;
			for(auto &T : adj[j]) {
				tie(A, B) = T;
				if(ind[A]) {
					X = B;
				}
				else {
					ans += solve(A) + B;
					Y = max(Y, B);
				}
			}
			if(X > Y) {
				O = min(O, X - Y);
			}
			else {
				ans += X - Y;
				F = true;
			}
		}
		if(C == n) {
			puts("0");
			return 0;
		}
		if(!F) ans += O;
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

telegraph.cpp: In function 'int main()':
telegraph.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
telegraph.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&d[i],&v[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:2:11: warning: 'first' may be used uninitialized in this function [-Wmaybe-uninitialized]
 #define X first
           ^~~~~
telegraph.cpp:2:11: note: 'first' was declared here
 #define X first
           ^
telegraph.cpp:48:7: note: in expansion of macro 'X'
    ll X, Y = 0, A, B;
       ^

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