Submission #93470

#	Time	Username	Problem	Language	Result	Execution time	Memory
93470		Flying_dragon_02	Telegraph (JOI16_telegraph)	C++14	100 / 100	88 ms	17896 KiB

telegraph

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
typedef pair<int, int> ii;

const int N = 1e5 + 5;
const int inf = 1e15;

int c[N], par[N], f[2], ck[N], val[N], ans, dp[N], n, lmao[N];

vector<int> graph[N], cycle, vec;

bool vis[N];

void dfs(int u) {
    if(lmao[u]) return ;
    vec.pb(u);
    if(vis[u] == 1) {
        int p = par[u];
        cycle.pb(u);
        while(p != u) {
            cycle.pb(p);
            p = par[p];
        }
        reverse(cycle.begin(), cycle.end());
        return ;
    }
    vis[u]++;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        par[v] = u;
        dfs(v);
    }
}

void bfs(int u) {
    vis[u] = 1;
    int mx = 0;
    for(int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if(ck[v]) continue;
        bfs(v);
        dp[u] += dp[v];
        dp[u] += c[v];
        mx = max(mx, c[v]);
    }
    dp[u] -= mx;
    val[u] = mx;
}

signed main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int p;
        cin >> p >> c[i];
        graph[p].pb(i);
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            vec.clear();
            cycle.clear();
            dfs(i);
            for(int j = 0; j < vec.size(); j++)
                lmao[vec[j]] = 1;
            if(cycle.size() == 0) continue;
            if(cycle.size() == n) {
                cout << "0\n";
                exit(0);
            }
            for(int j = 0; j < cycle.size(); j++)
                ck[cycle[j]] = 1;
            memset(f, 0, sizeof(f));
            f[1] = inf;
            int m = cycle.size();
            for(int j = 0; j < m; j++) {
                int u = cycle[j], nxt = cycle[(j + 1) % m];
                bfs(u);
                f[1] = min(f[1] + dp[cycle[j]] + val[cycle[j]], f[0] + dp[cycle[j]] + c[nxt]);
                f[0] = f[0] + dp[cycle[j]] + val[cycle[j]];
                f[0] = min(f[1], f[0]);
            }
            ans = ans + f[1];
        }
    }
    cout << ans;
}

Compilation message (stderr)

telegraph.cpp: In function 'void dfs(long long int)':
telegraph.cpp:34:11: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
     vis[u]++;
           ^~
telegraph.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
telegraph.cpp: In function 'void bfs(long long int)':
telegraph.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < graph[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~
telegraph.cpp: In function 'int main()':
telegraph.cpp:72:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vec.size(); j++)
                            ~~^~~~~~~~~~~~
telegraph.cpp:75:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(cycle.size() == n) {
                ~~~~~~~~~~~~~^~~~
telegraph.cpp:79:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < cycle.size(); j++)
                            ~~^~~~~~~~~~~~~~

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