Submission #152297

#	Time	Username	Problem	Language	Result	Execution time	Memory
152297		arnold518	Telegraph (JOI16_telegraph)	C++14	100 / 100	70 ms	13940 KiB

telegraph

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, A[MAXN+10], C[MAXN+10];
ll S, val;

vector<int> adj[MAXN+10];
int out[MAXN+10];

int vis[MAXN+10];

vector<vector<int>> cyc;
vector<int> ST;
void dfs(int now)
{
    vis[now]=1; ST.push_back(now);
    if(out[now]==-1) { vis[now]=2; ST.pop_back(); return; }
    if(vis[out[now]]==1) cyc.push_back(ST);
    if(vis[out[now]]==0) dfs(out[now]);
    vis[now]=2; ST.pop_back();
}

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<=N; i++)
    {
        scanf("%d%d", &A[i], &C[i]);
        adj[A[i]].push_back(i);
        S+=C[i];
    }

    memset(vis, 0, sizeof(vis));
    for(i=1; !vis[i]; i=A[i]) vis[i]=1;
    bool flag=true;
    if(i!=1) flag=false;
    for(i=1; i<=N; i++) flag=flag&&vis[i];
    if(flag) return !printf("0");

    for(i=1; i<=N; i++)
    {
        sort(adj[i].begin(), adj[i].end(), [&](const int &p, const int &q) { return C[p]>C[q]; });
        if(adj[i].empty()) out[i]=-1;
        else out[i]=adj[i][0], val+=C[out[i]];
    }

    memset(vis, 0, sizeof(vis));
    for(i=1; i<=N; i++) if(vis[i]==0) dfs(i);
    if(cyc.empty()) return !printf("%lld", S-val);

    for(auto &it : cyc)
    {
        ll now=-1e15;
        for(auto &jt : it)
        {
            if(adj[jt].size()==1) now=max(now, -(ll)C[adj[jt][0]]);
            else now=max(now, -(ll)C[adj[jt][0]]+(ll)C[adj[jt][1]]);
        }
        val+=now;
    }
    printf("%lld", S-val);
}

Compilation message (stderr)

telegraph.cpp: In function 'int main()':
telegraph.cpp:31:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
telegraph.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
telegraph.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &A[i], &C[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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