Submission #825834

#	Time	Username	Problem	Language	Result	Execution time	Memory
825834		PixelCat	Thousands Islands (IOI22_islands)	C++17	29 / 100	47 ms	15864 KiB

islands

#include "islands.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

vector<int> join(vector<int> v, vector<int> o, bool rev = false) {
    if(rev) reverse(all(o));
    v.insert(v.end(), all(o));
    return v;
}

const int MAXN = 100'000;
const int MAXM = 200'000;

vector<pii> adj[MAXN + 10];
vector<pii> rev[MAXN + 10];  // {node, edge id}

int scc[MAXN + 10];
pii path_to_0[MAXN + 10];  // how can node 0 reach this node? {node, edge id}

int vcnt[MAXN + 10];  // count of nodes
int ecnt[MAXN + 10];  // count of internal edges
int fi[MAXN + 10];  // first person on path to node 0

vector<int> stk;
void dfs1(int n) {
    scc[n] = -1;
    for(auto &e:rev[n]) if(scc[e.F] == 0) {
        dfs1(e.F);
    }
    stk.eb(n);
}
void dfs2(int n, int id) {
    scc[n] = id;
    vcnt[id]++;
    for(auto &e:adj[n]) {
        if(scc[e.F] == -1) dfs2(e.F, id);
        if(scc[e.F] == scc[n]) {
            ecnt[id]++;
        }
    }
}

void dfs_node0(int n) {
    // cerr << "owo? " << n << " " << scc[n] << " " << fi[scc[n]] << "\n";
    if(fi[scc[n]] < 0) fi[scc[n]] = n;
    for(auto &e:adj[n]) if(path_to_0[e.F].F == -1) {
        path_to_0[e.F] = pii(n, e.S);
        dfs_node0(e.F);
    }
}

pii par[MAXN + 10];  // {node, edge id}
int dep[MAXN + 10];
pii back_edge;
void dfs8(int n, int sccid, const set<int> &ban) {
    for(auto &i:adj[n]) if(scc[i.F] == sccid && !ban.count(i.S)) {
        if(dep[i.F] == 1) {
            back_edge = pii(n, i.S);
        } else if(dep[i.F] != 0) {
            ;
        } else {
            par[i.F] = pii(n, i.S);
            dep[i.F] = dep[n] + 1;
            dfs8(i.F, sccid, ban);
        }
    }
}
vector<int> find_cycle(int s, int sccid, vector<int> vban) {
    set<int> ban;
    for(auto &i:vban) ban.insert(i);
    fill(par, par + MAXN + 10, pii(-1, -1));
    memset(dep, 0, sizeof(dep));
    par[s] = pii(-8, -8);
    dep[s] = 1;
    back_edge = pii(-8, -8);
    dfs8(s, sccid, ban);

    // For(i, 0, 1) cerr << par[i].F << " \n"[i == 1];
    // For(i, 0, 1) cerr << par[i].F << " \n"[i == 1];
    // For(i, 0, 1) cerr << dep[i] << " \n"[i == 1];

    assert(back_edge.F != -8);
    vector<int> cyc;
    cyc.eb(back_edge.S);
    int cur = back_edge.F;
    while(cur != s) {
        cyc.eb(par[cur].S);
        cur = par[cur].F;
    }
    reverse(all(cyc));
    return cyc;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    // if (N == 4) {
    //   return vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
    // }
    // return false;

    For(i, 0, M - 1) {
        int x = U[i], y = V[i];
        adj[x].eb(y, i);
        rev[y].eb(x, i);
    }

    memset(scc, 0, sizeof(scc));
    For(i, 0, N - 1) if(scc[i] == 0) dfs1(i);
    int sccid = 0;
    while(sz(stk)) {
        sccid++;
        dfs2(stk.back(), sccid);
        while(sz(stk) && scc[stk.back()] != -1) stk.pop_back();
    }
    
    fill(fi, fi + MAXN + 10, -1);
    fill(path_to_0, path_to_0 + MAXN + 10, pii(-1, -1));
    path_to_0[0] = pii(-8, -8);
    dfs_node0(0);

    int good_id = -1;
    For(i, 1, sccid) if(fi[i] != -1 && ecnt[i] > vcnt[i]) {
        good_id = i; break;
    }
    // For(i, 0, N - 1) cerr << scc[i] << " \n"[i == N - 1];
    // For(i, 1, sccid) cerr << fi[i] << " \n"[i == sccid];
    // For(i, 0, N - 1) cerr << path_to_0[i].F << " \n"[i == N - 1];
    if(good_id < 0) return false;

    vector<int> cy1 = find_cycle(fi[good_id], good_id, {});
    vector<int> cy2 = find_cycle(fi[good_id], good_id, cy1);

    // for(auto &i:cy1) cerr << i << " ";
    // cerr << "\n";
    // for(auto &i:cy2) cerr << i << " ";
    // cerr << "\n";

    vector<int> chain;
    {
        int cur = fi[good_id];
        while(cur != 0) {
            chain.eb(path_to_0[cur].S);
            cur = path_to_0[cur].F;
        }
        reverse(all(chain));
    }

    vector<int> ans;
    ans = join(ans, chain);
    ans = join(ans, cy1);
    ans = join(ans, cy2);
    ans = join(ans, cy1, true);
    ans = join(ans, cy2, true);
    ans = join(ans, chain, true);
    return ans;
}

/*

4 5
0 1
1 2
2 3
0 3
3 1

1
10
0 1 2 4 0 3 2 1 4 3


2 3
0 1
1 0
1 0

0
0

*/

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 21
• Subtask 4: 24 / 24
• Subtask 5: 0 / 45