Submission #1301694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301694		dex111222333444555	Telegraph (JOI16_telegraph)	C++20	0 / 100	2 ms	576 KiB

telegraph

#include <bits/stdc++.h>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ii pair<int, int>
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define siz(v) (int)(v).size()
using namespace std;
const int infINT = 1e9 + 814, MAXN = 1e5 + 5, LOG = 20, mod = 1e9 + 7;
const long long inf = 1e18 + 734;
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
int numNode, nxt[MAXN], cost[MAXN];

void input(){
    cin >> numNode;
    for(int i = 1; i <= numNode; i++)
        cin >> nxt[i] >> cost[i];
}

namespace sub4{
    int par[MAXN], root[MAXN], low[MAXN], num[MAXN];
    long long best, sum, res, sumCost[MAXN], maxCycle[MAXN], dp[MAXN][3], pre[2][MAXN];
    bool visited[MAXN], inCycle[MAXN], haveCycle[MAXN];
    vector<int> adj[MAXN], radj[MAXN], cycle[MAXN];
    stack<int> st;

    bool checkSub(){
        return 1;
    }

    void tarjan(int u){
        st.push(u);
        low[u] = num[u] = ++num[0];
        for(int v: adj[u]) if (!visited[v]) {
            if (!num[v]){
                tarjan(v);
                minimize(low[u], low[v]);
            }else{
                minimize(low[u], num[v]);
            }
        }
        if (low[u] != num[u]) return;
        int v, pre = u;
        vector<int> can;
        do{
            v = st.top(); visited[v] = 1;
            can.push_back(v);
            st.pop();
        }while(u != v);
        int k = siz(can);
        if (k <= 1) return;
        for(int i = 0; i < k; i++){
            int j = (i + 1 + k) % k;
            par[can[i]] = can[j];
            inCycle[can[i]] = 1;
            cycle[u].push_back(can[i]);
        }
    }

    long long calcDP(vector<int> can){
        can.insert(begin(can), 0);
        can[0] = can.back();
        int k = siz(can) - 1;
        long long mx = -1, res = -1, mx2 = -1;
        for(int i = 1; i <= k; i++)
            pre[0][i] = pre[0][i - 1] + dp[can[i]][2] + cost[can[i - 1]],
            pre[1][i] = pre[1][i - 1] + dp[can[i]][0];
        for(int i = 1; i <= k; i++){
            maximize(mx, pre[0][i - 1] - pre[1][i - 1]);
//            maximize(mx2, pre[1][i - 1] - pre[0][i - 1]);
            maximize(res, pre[1][i] - pre[0][i] + pre[0][k] + mx);
//            maximize(res, pre[0][i] - pre[1][i] + pre[1][k] + mx2);
        }

        return res;
    }

    void dfsOut(int u, int r){
        long long sum = 0, best = 0;
        for(int v: radj[u]) if (!inCycle[v]){
            dfsOut(v, r);
            sum += dp[v][0];
            maximize(best, dp[v][1] - dp[v][0]);
        }
        dp[u][1] = sum + best + cost[u];
        dp[u][0] = sum + best;
        dp[u][2] = sum;
    }

    void solve(){
        for(int i = 1; i <= numNode; i++){
            int u = i, v = nxt[i];
            adj[u].push_back(v);
            radj[v].push_back(u);
        }
        int cntComp = 0;
        for(int i = 1; i <= numNode; i++){
            if (!visited[i]) tarjan(i), cntComp++;
            sum += cost[i];
        }
        int cnt = 0;
//        for(int i = 1; i <= numNode; i++) cout << inCycle[i] << ' '; cout << '\n';
        for(int i = 1; i <= numNode; i++){
            if (inCycle[i]) dfsOut(i, i), cnt++;
            int mi = infINT;
            for(int x: cycle[i]){
                sumCost[i] += cost[x];
                mi = min(mi, cost[x]);
            }
            maxCycle[i] = sumCost[i] - mi;
        }
//        for(int i = 0; i < 2; i++)
//        for(int u = 1; u <= numNode; u++)
//        cout << dp[u][i] << " \n"[u == numNode];
//        for(int i = 1; i <= numNode; i++) cout << par[i] << ' '; cout << '\n';
        if (cntComp == 1 && cnt == numNode) return cout << 0 << '\n', void();
        long long dir = 0;
        for(int i = 1; i <= numNode; i++){
            best = 0;
            if (inCycle[i]) dir += dp[i][0];
            reverse(all(cycle[i]));
            for(int u: cycle[i]){
                maximize(best, dp[u][1] + sumCost[i] - cost[u] - cost[par[u]]);
                maximize(best, dp[u][2] + maxCycle[i]);
//                cout << u << ' ';
            }
//            cout << i << ": \n" << calcDP(cycle[i]) << '\n';
            maximize(best, calcDP(cycle[i]));
            vector<int> tmp;
            for(int j = 1; j < siz(cycle[i]); j++) tmp.push_back(cycle[i][j]);
            if (cycle[i].size()) tmp.push_back(cycle[i][0]);
            maximize(best, calcDP(tmp));
            vector<int> tmp2;
            for(int j = 1; j < siz(tmp); j++) tmp2.push_back(tmp[j]);
            if (tmp.size()) tmp2.push_back(tmp[0]);
            maximize(best, calcDP(tmp2));
            res += best;
        }
        cout << sum - max(dir, res) << '\n';
    }

}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    input();
    if (sub4::checkSub()) sub4::solve();
}

Compilation message (stderr)

telegraph.cpp: In function 'int main()':
telegraph.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
telegraph.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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