제출 #628952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
628952		peti1234	수천개의 섬 (IOI22_islands)	C++17	19.25 / 100	1063 ms	38756 KiB

islands

#include<bits/stdc++.h>
//#include "islands.h"

bool test=0;


using namespace std;
const int c=300005, k=20;
int n, m, szint[c], fel[c], felel[c], fel2[c][k], bal[c], jobb[c], kezd, veg, specid;
vector<int> alaput, alapkor, ans, ut2;
vector<pair<int, int> > sz[c];
bool kesz, v[c], v2[c][2], korben[c], uton[c];
void nullazas() {
    for (int i=1; i<=n; i++) {
        szint[i]=0, fel[i]=0, felel[i]=0;
        v[i]=0, v2[i][0]=0, v2[i][1]=0, korben[i]=0, uton[i]=0;
        for (int j=0; j<k; j++) fel2[i][j]=0;
    }
    alaput.clear(), alapkor.clear(), ans.clear(), ut2.clear();
    kezd=0, veg=0, specid=0;
}
int lca(int a, int b) {
    if (szint[a]<szint[b]) swap(a, b);
    for (int i=k-1; i>=0; i--) {
        if (szint[fel2[a][i]]>=szint[b]) a=fel2[a][i];
    }
    for (int i=k-1; i>=0; i--) {
        if (fel2[a][i]!=fel2[b][i]) {
            a=fel2[a][i], b=fel2[b][i];
        }
    }
    if (a==b) return a;
    return fel2[a][0];
}
void conc(vector<int> & a, vector<int> b) {
    for (auto x:b) {
        a.push_back(x);
    }
}
vector<int> valt(vector<int> a) {
    vector<int> b;
    for (auto x:a) {
        if (b.size()>0 && b.back()==x) b.pop_back();
        else b.push_back(x);
    }
    return b;
}
vector<int> calc(int a, int b) {
    assert(lca(a, b)==b);
    vector<int> res;
    while (a!=b) {
        res.push_back(felel[a]);
        a=fel[a];
    }
    return res;
}
void ket_kor(int a, int b, int c, int d) {
    if (test) cout << "ket kor\n" << "\n";
    // a-b es b-d a ket specialis el, b es d nek nagyobb a szintje
    if (kesz) return;
    kesz=true;
    for (int i=0; i<2; i++) {
        vector<int> ut=calc(a, 1);
        reverse(ut.begin(), ut.end());
        conc(ans, ut);
        vector<int> kor=calc(b, a);
        reverse(kor.begin(), kor.end());
        bool jo=0;
        for (auto p:sz[b]) {
            if (p.first==a) {
                kor.push_back(p.second);
                jo=1;
                break;
            }
        }
        assert(jo);
        if (i==1) reverse(kor.begin(), kor.end());
        conc(ans, kor);
        reverse(ut.begin(), ut.end());
        conc(ans, ut);


        ut=calc(c, 1);
        reverse(ut.begin(), ut.end());
        conc(ans, ut);
        kor=calc(d, c);
        reverse(kor.begin(), kor.end());
        jo=0;
        for (auto p:sz[d]) {
            if (p.first==c) {
                kor.push_back(p.second);
                jo=1;
                break;
            }
        }
        assert(jo);
        if (i==1) reverse(kor.begin(), kor.end());
        conc(ans, kor);
        reverse(ut.begin(), ut.end());
        conc(ans, ut);
    }
}

void egy_kor() {
    if (test) cout << "egy kor\n";
    assert(!kesz);
    kesz=1;
    int pos=jobb[ut2.back()];
    assert(korben[pos]);
    // alaput, alapkor, ut2, pos
    if (test) {
        cout << "alaput: ";
        for (auto x:alaput) cout << x << " ";
        cout << "\n";
    }
    conc(ans, alaput);
    conc(ans, alapkor);
    conc(ans, calc(kezd, 1));
    conc(ans, ut2);

    int si=alapkor.size(), kezd=-1;
    for (int i=0; i<si; i++) {
        if (jobb[alapkor[i]]==pos) {
            kezd=i;
        }
    }
    assert(kezd!=-1);
    for (int i=0; i<si; i++) {
        int id=(kezd-i+si)%si;
        ans.push_back(alapkor[id]);
    }

    reverse(ut2.begin(), ut2.end());
    conc(ans, ut2);
    reverse(ut2.begin(), ut2.end());
}


void dfs(int a) {
    if (test) cout << "dfs " << a << "\n";
    v[a]=true;
    fel2[a][0]=fel[a];
    for (int i=1; i<k; i++) {
        fel2[a][i]=fel2[fel2[a][i-1]][i-1];
    }

    for (auto p:sz[a]) {
        int x=p.first, y=p.second;
        if (test) cout << "fontos " << x << " " << y << "\n";
        if (!v[x]) {
            szint[x]=szint[a]+1;
            fel[x]=a, felel[x]=y;
            dfs(x);
        } else {
            int cs=lca(a, x);
            if (cs!=x) continue;
            if (kezd==0) {
                kezd=x, veg=a, specid=y;
            } else {
                int s=lca(kezd, x), t=lca(veg, a);
                if (s==t) {
                    ket_kor(kezd, veg, x, a);
                } else {
                    assert(s==kezd || s==x);
                    if (s==kezd) kezd=x, veg=a, specid=y;
                }
            }
        }
    }
}

void dfs2(int a, bool b) {
    v2[a][b]=1, uton[a]=1;
    if (korben[a] && b && !kesz) {
        egy_kor();
    }
    for (auto p:sz[a]) {
        int x=p.first, y=p.second;
        if (uton[x]) continue;
        int su=alaput.size(), su2=ut2.size();
        if (su==su2 && b==0 && y==alapkor[0]) continue;

        bool kov=b;
        if (su<=su2 || y!=alaput[su2]) kov=1;
        if (!v2[x][kov]) {
            ut2.push_back(y);
            dfs2(x, kov);
            assert(ut2.back()==y);
            ut2.pop_back();
        }
    }
    uton[a]=0;
}

variant<bool, vector<int>> find_journey(
//bool find_journey(
    int N, int M, vector<int> U, vector<int> V) {

    n=N, m=M;
    for (int i=0; i<m; i++) {
        int a=U[i], b=V[i];
        sz[a+1].push_back({b+1, i});
        bal[i]=a+1, jobb[i]=b+1;
    }
    for (int proba=0; proba<20; proba++) {
        szint[1]=1;
        dfs(1);
        if (test) cout << "vege " << kezd << " " << veg << "\n";
        if (kezd==0) {
            return false;
        }
        alaput=calc(kezd, 1);
        reverse(alaput.begin(), alaput.end());
        alapkor=calc(veg, kezd);
        for (auto x:alapkor) {
            korben[bal[x]]=1, korben[jobb[x]]=1;
        }
        reverse(alapkor.begin(), alapkor.end());
        alapkor.push_back(specid);

        assert(alapkor.size()>0);
        if (!kesz) {
            dfs2(1, 0);
        }
        if (kesz) {
            break;
        }

        nullazas();
        for (int i=1; i<=n; i++) {
            random_shuffle(sz[i].begin(), sz[i].end());
        }
    }
    if (!kesz) {
        return false;
    } else {
        ans=valt(ans);
        assert(ans.size()>0);
        //return ans;
        return true;
    }
}
/*
int main() {
    int nn, mm;
    vector<int> aa, bb;
    cin >> nn >> mm;
    for (int i=0; i<mm; i++) {
        int x, y;
        cin >> x >> y;
        aa.push_back(x), bb.push_back(y);
    }
    bool res=find_journey(nn, mm, aa, bb);
    cout << "sikerult: " << res << "\n";
    for (auto x:ans) {
        cout << x << " ";
    }
    cout << "\n";
    return 0;
}
*/
/*
7
9
0 1 1 2 2 3 3 4 4 5 5 6
4 2
1 5
6 1
*/

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