Submission #55118

#	Time	Username	Problem	Language	Result	Execution time	Memory
55118		ainta	Telegraph (JOI16_telegraph)	C++17	100 / 100	110 ms	8424 KiB

telegraph

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>E[101000];
int n, C[101000], w[101000], Deg[101000], Q[101000], head, tail, v[101000], chk;
long long res;
void Do(int a) {
	int t = a, i, rr = 1e9;
	vector<int>T;
	while (1) {
		v[t] = 1;
		T.push_back(t);
		t = w[t];
		if (t == a)break;
	}
	if (T.size() == n) {
		chk = 1;
		return;
	}
	for (auto &x : T) {
		int Mx1 = -1, Mx2 = 0;
		for (auto &y : E[x]) {
			if (Deg[y])Mx1 = max(Mx1, C[y]);
			else Mx2 = max(Mx2, C[y]);
		}
		rr = min(rr, Mx1 - Mx2);
	}
	rr = max(rr, 0);
	res += rr;
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &w[i],&C[i]);
		Deg[w[i]]++;
		E[w[i]].push_back(i);
	}
	for (i = 1; i <= n; i++) {
		vector<int>T;
		for (auto &t : E[i]) {
			T.push_back(C[t]);
		}
		if (!T.empty()) {
			sort(T.begin(), T.end());
			for (int j = 0; j < T.size() - 1; j++) {
				res += T[j];
			}
		}
	}
	for (i = 1; i <= n; i++)if (!Deg[i])Q[++tail] = i;
	while (head < tail) {
		int x = Q[++head];
		v[x] = 1;
		Deg[w[x]]--;
		if (!Deg[w[x]])Q[++tail] = w[x];
	}
	for (i = 1; i <= n; i++) {
		if (!v[i]) {
			Do(i);
		}
	}
	if (chk) {
		printf("0\n");
		return 0;
	}
	printf("%lld\n", res);
}

Compilation message (stderr)

telegraph.cpp: In function 'void Do(int)':
telegraph.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (T.size() == n) {
      ~~~~~~~~~^~~~
telegraph.cpp:9:13: warning: unused variable 'i' [-Wunused-variable]
  int t = a, i, rr = 1e9;
             ^
telegraph.cpp: In function 'int main()':
telegraph.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < T.size() - 1; j++) {
                    ~~^~~~~~~~~~~~~~
telegraph.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
telegraph.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i],&C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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