Submission #105718

#	Time	Username	Problem	Language	Result	Execution time	Memory
105718		Pro_ktmr	Telegraph (JOI16_telegraph)	C++14	100 / 100	201 ms	15712 KiB

telegraph

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int N;
int A[100000];
LL C[100000];

vector<int> saki[100000];

bool already[100000] = {};
int sizeOfCycle = 0;
int belongCycle[100000];
vector<int> cycle[100000];
vector<int> st;
void dfs(int now){
	if(already[A[now]]){
		bool flg = false;
		for(int i=0; i<st.size(); i++){
			if(st[i] == A[now]) flg = true;
			if(flg){
				belongCycle[st[i]] = sizeOfCycle;
				cycle[sizeOfCycle].push_back(st[i]);
			}
		}
		if(flg) sizeOfCycle++;
	}
	else{
		already[A[now]] = true;
		st.push_back(A[now]);
		dfs(A[now]);
		st.pop_back();
	}
}

LL ans;
int main(){
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> A[i] >> C[i];
		A[i]--;
		belongCycle[i] = -1;
		saki[A[i]].push_back(i);
	}
	for(int i=0; i<N; i++){
		if(already[i]) continue;
		already[i] = true;
		st.push_back(i);
		dfs(i);
		st.pop_back();
	}
	/*for(int i=0; i<sizeOfCycle; i++){
		for(int j=0; j<cycle[i].size(); j++) cout << cycle[i][j] << " ";
		cout << endl;
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<saki[i].size(); j++) cout << saki[i][j] << " ";
		cout << endl;
	}*/
	
	if(sizeOfCycle == 1 && cycle[0].size() == N){
		cout << 0 << endl;
		return 0;
	}
	
	ans = 0;
	for(int i=0; i<sizeOfCycle; i++){
		LL ansOfCycle = LLONG_MAX;
		LL tmp = 0;
		for(int k=0; k<cycle[i].size(); k++){
			LL sum = 0;
			LL m = 0;
			for(int l=0; l<saki[cycle[i][k]].size(); l++){
				sum += C[saki[cycle[i][k]][l]];
				m = max(m, C[saki[cycle[i][k]][l]]);
			}
			tmp += sum - m;
		}
		for(int j=0; j<cycle[i].size(); j++){
			LL sum = 0;
			LL m = 0;
			for(int l=0; l<saki[ A[cycle[i][j]] ].size(); l++){
				sum += C[ saki[ A[cycle[i][j]] ][l] ];
				m = max(m, C[ saki[ A[cycle[i][j]] ][l] ]);
			}
			LL c1 = sum - m;
			
			sum = 0;
			m = 0;
			for(int l=0; l<saki[ A[cycle[i][j]] ].size(); l++){
				if(saki[ A[cycle[i][j]] ][l] == cycle[i][j]) continue;
				sum += C[ saki[ A[cycle[i][j]] ][l] ];
				m = max(m, C[ saki[ A[cycle[i][j]] ][l] ]);
			}
			LL c2 = sum - m;
			ansOfCycle = min(ansOfCycle, tmp-c1+c2+C[cycle[i][j]]);
		}
		ans += ansOfCycle;
	}
	for(int i=0; i<N; i++){
		if(belongCycle[i] >= 0) continue;
		LL sum = 0;
		LL m = 0;
		for(int j=0; j<saki[i].size(); j++){
			sum += C[saki[i][j]];
			m = max(m, C[saki[i][j]]);
		}
		ans += sum - m;
	}
	cout << ans << endl;
	
	return 0;
}

Compilation message (stderr)

telegraph.cpp: In function 'void dfs(int)':
telegraph.cpp:19:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<st.size(); i++){
                ~^~~~~~~~~~
telegraph.cpp: In function 'int main()':
telegraph.cpp:61:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(sizeOfCycle == 1 && cycle[0].size() == N){
                         ~~~~~~~~~~~~~~~~^~~~
telegraph.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<cycle[i].size(); k++){
                ~^~~~~~~~~~~~~~~~
telegraph.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int l=0; l<saki[cycle[i][k]].size(); l++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<cycle[i].size(); j++){
                ~^~~~~~~~~~~~~~~~
telegraph.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int l=0; l<saki[ A[cycle[i][j]] ].size(); l++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int l=0; l<saki[ A[cycle[i][j]] ].size(); l++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:104:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<saki[i].size(); j++){
                ~^~~~~~~~~~~~~~~

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