oj.uz

Submission #134623

# Submission time Handle Problem Language Result Execution time Memory
134623 2019-07-23T05:46:12 Z 임유진(#3241) Telegraph (JOI16_telegraph) C++14
0 / 100
 6 ms 5112 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

const int MAXN = 100005;
const int INF = 1 << 30;
const lint LINF = 1ll << 60;

int A[MAXN], C[MAXN];
bool chk[MAXN], cyc[MAXN];
int cycn;
vector<int> chi[MAXN], cn[MAXN];
int mx[MAXN], mxt[MAXN];

void chkcyc(int x, int c) {
	cyc[x] = true;
	cn[c].push_back(x);
	if(!cyc[A[x]]) chkcyc(A[x], c);
}

void dfs(int x) {
	chk[x] = true;
	if(chk[A[x]]) chkcyc(x, ++cycn);
	else dfs(A[x]);
}

void chktree(int x) {
	chk[x] = true;
	for(auto a : chi[x]) if(!chk[a]) chktree(a);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	int N;
	lint ans = 0ll;

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i] >> C[i];

	for(int i = 1; i <= N; i++) chi[A[i]].push_back(i);
	for(int i = 1; i <= N; i++) if(!chk[i] && chi[i].empty()) {
		dfs(i);
		for(auto a : cn[cycn]) chktree(a);
	}
	for(int i = 1; i <= N; i++) if(!chk[i]) dfs(i);

	/*
	for(int i = 1; i <= cycn; i++) {
		printf("cn[%d] = [", i);
		for(auto a : cn[i]) printf("%d ", a);
		printf("]\n");
	}
	*/

	bool b = true;
	for(int i = 1; i <= N; i++) if(!cyc[i]) b = false;
	if(b && cycn == 1) {
		cout << 0;
		return 0;
	}

	for(int i = 1; i <= N; i++) {
		for(auto a : chi[i]) {
			ans += C[a];
			mx[i] = max(mx[i], C[a]);
		}
		ans -= mx[i];
	}
	for(int i = 1; i <= N; i++) if(!cyc[i]) mxt[A[i]] = max(mxt[A[i]], C[i]);

	for(int i = 1; i <= cycn; i++) {
		bool b = true;
		for(int j = 0; j < cn[i].size(); j++) if(mx[cn[i][(j + 1) % cn[i].size()]] != C[cn[i][j]]) b = false;
		if(!b) continue;
		int mn = INF;
		for(int j = 0; j < cn[i].size(); j++) 
			mn = min(mn, mx[cn[i][j]] - mxt[cn[i][j]]);
		ans += mn;
	}

	cout << ans;
	return 0;
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cn[i].size(); j++) if(mx[cn[i][(j + 1) % cn[i].size()]] != C[cn[i][j]]) b = false;
                  ~~^~~~~~~~~~~~~~
telegraph.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cn[i].size(); j++)
                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -