oj.uz

Submission #511866

# Submission time Handle Problem Language Result Execution time Memory
511866 2022-01-16T04:54:32 Z 79brue Telegraph (JOI16_telegraph) C++14
0 / 100
 1 ms 2636 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    ll x, c;
    Edge(){}
    Edge(ll x, ll c): x(x), c(c){}

    bool operator<(const Edge &r)const{
        return c > r.c;
    }
};

int n; ll sum;
int arr[100002];
ll cost[100002];
vector<Edge> from[100002];

bool visited[100002];
bool visited2[100002];
vector<int> component;

void traverse(int x){
    if(x<1 || visited[x]) return;
    component.push_back(x);
    visited[x] = 1;
    for(auto y: from[x]) traverse(y.x);
    traverse(arr[x]);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %lld", &arr[i], &cost[i]);
        sum += cost[i];
        from[arr[i]].push_back(Edge(i, cost[i]));
        from[i].push_back(Edge(-1, 0));
    }
    for(int i=1; i<=n; i++) sort(from[i].begin(), from[i].end());

    for(int i=1; i<=n; i++){
        if(visited[i]) continue;
        component.clear();
        traverse(i);

        /// 1. 사이클을 찾는다.
        vector<int> cycle;
        int tmp = i;
        while(!visited2[tmp]){
            visited2[tmp] = 1;
            cycle.push_back(tmp);
            tmp = arr[tmp];
        }
        cycle.erase(cycle.begin(), find(cycle.begin(), cycle.end(), tmp));

        if((int)cycle.size() == n){
            printf("0");
            return 0;
        }

        /// 2. 사이클 조건이 없을 때의 답을 찾는다.
        ll firstAns = 0;
        ll compAns = 0;
        for(auto x: component){
            firstAns += from[x][0].c;
        }

        /// 3. 사이클 조건을 넣고 답을 찾는다.
        for(auto x: cycle){
            compAns = max(compAns, firstAns - from[x][0].c + from[x][1].c);
        }

        sum -= compAns;
    }

    printf("%lld", sum);
}

Compilation message

telegraph.cpp: In function 'int main()':
telegraph.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
telegraph.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d %lld", &arr[i], &cost[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Halted 0 ms 0 KB -