Submission #1070659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070659		Mihailo	Thousands Islands (IOI22_islands)	C++17	100 / 100	443 ms	70592 KiB

islands

#include <bits/stdc++.h>
#include <variant>
#include <vector>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000002022ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;

multiset<ll> to[100100], from[100100];
map<pll, vector<ll>> edgenames;
set<ll> obidjeni, ciklus, obidjeni2, ciklus2;
vector<int> braket;
ll root, sled[100100], pre[100100], sled2[100100], pre2[100100];
bool dead[100100];
string s;

void erase(ll cur) {
    if(dead[cur]) return;
    vector<ll> kill;
    for(auto i:to[cur]) {
        from[i].erase(from[i].find(cur));
        if(i!=root&&from[i].empty()) kill.pb(i);
    }
    for(auto i:from[cur]) {
        to[i].erase(to[i].find(cur));
        if(to[i].empty()) kill.pb(i);
    }
    dead[cur]=true;
    for(auto i:kill) erase(i);
}

void put(ll cur, ll pr) {
    if(obidjeni.count(cur)) {
        pre[cur]=pr;
        while(pr!=cur) {
            ciklus.insert(pr);
            pr=pre[pr];
        }
        ciklus.insert(cur);
        return;
    }
    pre[cur]=pr;
    sled[cur]=*to[cur].begin();
    obidjeni.insert(cur);
    put(*to[cur].begin(), cur);
}

void drugiput(ll cur, ll pr) {
    if(cur!=root&&ciklus.count(cur)) {
        pre2[cur]=pr;
        s="IstiCiklus";
        return;
    }
    if(obidjeni2.count(cur)) {
        pre2[cur]=pr;
        while(pr!=cur) {
            ciklus2.insert(pr);
            pr=pre2[pr];
        }
        ciklus2.insert(cur);
        return;
    }
    pre2[cur]=pr;
    obidjeni2.insert(cur);
    if(cur==root) sled2[cur]=*next(to[cur].begin());
    else sled2[cur]=*to[cur].begin();
    if(cur==root) drugiput(*next(to[cur].begin()), cur);
    else drugiput(*to[cur].begin(), cur);
}

vector<ll> veca, zapravo;

void ispisiput(ll cur) {
    if(!ciklus.count(cur)) {
        veca.pb(edgenames[mp(cur, sled[cur])][0]);
        ispisiput(sled[cur]);
        return;
    }
    zapravo=veca;
    ll tr=cur;
    zapravo.pb(edgenames[mp(tr, sled[tr])][0]);
    tr=sled[tr];
    while(tr!=cur) {
        zapravo.pb(edgenames[mp(tr, sled[tr])][0]);
        tr=sled[tr];
    }
    while(veca.size()) {
        zapravo.pb(veca.back());
        veca.pop_back();
    }
}

void ispisiputnazad(ll cur) {
    if(!ciklus.count(cur)) {
        veca.pb(edgenames[mp(cur, sled[cur])][0]);
        ispisiputnazad(sled[cur]);
        return;
    }
    zapravo=veca;
    ll tr=cur;
    zapravo.pb(edgenames[mp(pre[tr], tr)][0]);
    tr=pre[tr];
    while(tr!=cur) {
        zapravo.pb(edgenames[mp(pre[tr], tr)][0]);
        tr=pre[tr];
    }
    while(veca.size()) {
        zapravo.pb(veca.back());
        veca.pop_back();
    }
}

void ispisidrugiput(ll cur) {
    if(cur!=root&&ciklus.count(cur)) {
        zapravo=veca;
        ll tr=cur;
        zapravo.pb(edgenames[mp(pre[tr], tr)][0]);
        tr=pre[tr];
        while(tr!=cur) {
            zapravo.pb(edgenames[mp(pre[tr], tr)][0]);
            tr=pre[tr];
        }
        while(veca.size()) {
            zapravo.pb(veca.back());
            veca.pop_back();
        }
        return;
    }
    if(!ciklus2.count(cur)) {
        if(cur==root) {
            veca.pb(edgenames[mp(cur, sled2[cur])].back());
        }
        else veca.pb(edgenames[mp(cur, sled2[cur])][0]);
        ispisidrugiput(sled2[cur]);
        return;
    }
    zapravo=veca;
    ll tr=cur;
    zapravo.pb(edgenames[mp(tr, sled2[tr])][0]);
    tr=sled2[tr];
    while(tr!=cur) {
        zapravo.pb(edgenames[mp(tr, sled2[tr])][0]);
        tr=sled2[tr];
    }
    while(veca.size()) {
        zapravo.pb(veca.back());
        veca.pop_back();
    }
}

void ispisidrugiputnazad(ll cur) {
    if(!ciklus2.count(cur)) {
        if(cur==root) {
            veca.pb(edgenames[mp(cur, sled2[cur])].back());
        }
        else veca.pb(edgenames[mp(cur, sled2[cur])][0]);
        ispisidrugiputnazad(sled2[cur]);
        return;
    }
    zapravo=veca;
    ll tr=cur;
    zapravo.pb(edgenames[mp(pre2[tr], tr)][0]);
    tr=pre2[tr];
    while(tr!=cur) {
        zapravo.pb(edgenames[mp(pre2[tr], tr)][0]);
        tr=pre2[tr];
    }
    while(veca.size()) {
        zapravo.pb(veca.back());
        veca.pop_back();
    }
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    variant<bool, vector<int>> v;
    for(int i=0; i<M; i++) {
        to[U[i]].insert(V[i]);
        from[V[i]].insert(U[i]);
        edgenames[mp(U[i], V[i])].pb(i);
    }
    for(int i=0; i<N; i++) {
        if(to[i].empty()||(i!=root&&from[i].empty())) erase(i);
    }
    if(dead[root]) {
        v=false;
        return v;
    }
    while(to[root].size()==1) {
        ll t=root;
        root=*to[root].begin();
        braket.pb(edgenames[mp(t, root)][0]);
        erase(t);
        if(dead[root]) {
            v=false;
            return v;
        }
    }
    v=true;
    put(root, root);
    drugiput(root, root);
    if(s=="") {
        vector<int> dobar;
        dobar=braket;
        ispisiput(root);
        for(int i:zapravo) dobar.pb(i);
        zapravo.clear();
        ispisidrugiput(root);
        for(int i:zapravo) dobar.pb(i);
        zapravo.clear();
        ispisiputnazad(root);
        for(int i:zapravo) dobar.pb(i);
        zapravo.clear();
        ispisidrugiputnazad(root);
        for(int i:zapravo) dobar.pb(i);
        zapravo.clear();
        while(braket.size()) {
            dobar.pb(braket.back());
            braket.pop_back();
        }
        v=dobar;
    }
    else {
        vector<int> dobar;
        dobar=braket;
        ispisiput(root);
        for(int i:zapravo) dobar.pb(i);
        zapravo.clear();
        ispisidrugiput(root);
        for(int i:zapravo) dobar.pb(i);
        zapravo.clear();
        while(braket.size()) {
            dobar.pb(braket.back());
            braket.pop_back();
        }
        v=dobar;
    }
    return v;
}

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