Submission #511878

#	Time	Username	Problem	Language	Result	Execution time	Memory
511878		79brue	Telegraph (JOI16_telegraph)	C++14	100 / 100	86 ms	16596 KiB

telegraph

#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 inCycle[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));
        for(auto c: cycle) inCycle[c] = 1;

        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 + (inCycle[from[x][0].x] ? from[x][1].c : from[x][0].c));
        }

        sum -= compAns;
    }

    printf("%lld", sum);
}

Compilation message (stderr)

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

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