oj.uz

Submission #134881

# Submission time Handle Problem Language Result Execution time Memory
134881 2019-07-23T11:21:24 Z onjo0127 Telegraph (JOI16_telegraph) C++11
0 / 100
 4 ms 2680 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL * 1e18;
int N, A[100009], C[100009], D[100009];
bool fin[100009], vs[100009];
vector<int> S, T[100009];
vector<vector<int> > R;
long long ans;

void go(int x) {
	S.push_back(x);
	vs[x] = 1;
	if(vs[A[x]]) {
		if(!fin[x]) {
			bool f = 0;
			vector<int> stk;
			while(S.size()) {
				int tmp = S.back(); S.pop_back();
				stk.push_back(tmp);
				if(tmp == A[x]) {
					f = 1;
					break;
				}
			}
			if(f) {
				for(auto& it: stk) fin[it] = 1;
				reverse(stk.begin(), stk.end());
				R.push_back(stk);
			}
		}
	}
	else go(A[x]);
}

void dfs(int x) {
	D[x] = 0;
	long long s = 0;
	for(auto& it: T[x]) {
		dfs(it);
		D[x] = max(D[x], C[it]);
		s += C[it];
	}
	ans += s - D[x];
}

int main() {
	scanf("%d",&N);
	for(int i=1; i<=N; i++) scanf("%d%d",&A[i],&C[i]);
	for(int i=1; i<=N; i++) if(!vs[i]) go(i);
		
	// printf("rings: %d\n", R.size());
	// for(auto& it: R) {
	// 	puts("ring");
	// 	for(auto& jt: it) printf("%d ",jt);
	// 	puts("");
	// }
	// puts("\n");

	bool f = 1;
	for(int i=1; i<=N; i++) if(!fin[i]) {
		// printf("tree edge: %d -> %d\n", A[i], i);
		T[A[i]].push_back(i);
		f = 0;
	}
	if(f && (int)R.size() == 1) return !printf("0");
	for(int i=1; i<=N; i++) if(fin[i]) dfs(i);
	for(auto& it: R) {
		long long mn = INF;
		for(int i=0; i<it.size(); i++) {
			long long s = 0;
			int pr = it[i];
			for(int j=i+1; j<it.size(); j++) {
				s += min(C[pr], D[it[j]]);
				pr = it[j];
			}
			for(int j=0; j<i; j++) {
				s += min(C[pr], D[it[j]]);
				pr = it[j];
			}
			s += C[pr];
			mn = min(mn, s);
		}
		ans += mn;
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<it.size(); i++) {
                ~^~~~~~~~~~
telegraph.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=i+1; j<it.size(); j++) {
                   ~^~~~~~~~~~
telegraph.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
telegraph.cpp:49:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d%d",&A[i],&C[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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