#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3ffffffffffffff;
bool ch[100009];
int a[100009], c[100009];
vector<int> route;
vector<int> graph[100009];
ll cyc[100009];
ll sum[100009], mx[100009], mx2[100009];
void findcycle(int v){
// printf("v=%d\n", v);
route.push_back(v);
if(ch[v]){
int i;
for(i=0; i<route.size(); i++){
if(route[i] == v)
break;
}
for(; i+1<route.size(); i++){
cyc[route[i+1]] = c[route[i]];
}
return;
}
ch[v] = 1;
findcycle(a[v]);
}
void dfs(int v){
if(ch[v])
return;
route.push_back(v);
ch[v]=1;
for(int i=0; i<graph[v].size(); i++)
dfs(graph[v][i]);
}
int main(){
int n, i, comp = 0;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d %d", &a[i], &c[i]);
graph[i].push_back(a[i]);
graph[a[i]].push_back(i);
if(c[i] > mx[a[i]]){
mx2[a[i]] = mx[a[i]];
mx[a[i]] = c[i];
}
else if(c[i] > mx2[a[i]]){
mx2[a[i]] = c[i];
}
sum[a[i]] += c[i];
}
for(i=1; i<=n; i++){
route.clear();
findcycle(i);
}
ll ans = 0;
memset(ch, 0, sizeof(ch));
for(i=1; i<=n; i++){
if(!ch[i]){
comp++;
route.clear();
dfs(i);
int j;
ll temp = 0, mn = INF;
bool flag=0;
for(j=0; j<route.size(); j++){
//printf("cyc=%d\n", cyc[route[j]]);
if(cyc[route[j]])
mn = min(mn, cyc[route[j]]);
if(!mx2[route[j]])
continue;
temp += sum[route[j]] - mx[route[j]];
if(cyc[route[j]] && mx[route[j]] && cyc[route[j]] != mx[route[j]])
flag = 1;
mn = min(mn, mx[route[j]] - mx2[route[j]]);
}
//printf("i=%d temp=%lld mn=%lld\n", i, temp, mn);
if(!flag)
temp += mn;
ans += temp;
}
}
if(comp==1){
for(i=1; i<=n; i++){
if(!cyc[i])
break;
}
if(i==n+1){
ans=0;
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
telegraph.cpp: In function 'void findcycle(int)':
telegraph.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(i=0; i<route.size(); i++){
| ~^~~~~~~~~~~~~
telegraph.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(; i+1<route.size(); i++){
| ~~~^~~~~~~~~~~~~
telegraph.cpp: In function 'void dfs(int)':
telegraph.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0; i<graph[v].size(); i++)
| ~^~~~~~~~~~~~~~~~
telegraph.cpp: In function 'int main()':
telegraph.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(j=0; j<route.size(); j++){
| ~^~~~~~~~~~~~~
telegraph.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
telegraph.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d %d", &a[i], &c[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
