Submission #628463

#	Time	Username	Problem	Language	Result	Execution time	Memory
628463		peti1234	Thousands Islands (IOI22_islands)	C++17	10 / 100	127 ms	22208 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];
 
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) {
    // 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());
        for (auto p:sz[b]) {
            bool jo=0;
            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());
        for (auto p:sz[d]) {
            bool jo=0;
            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() {
    assert(!kesz);
    kesz=1;
    int pos=jobb[ut2.back()];
    assert(korben[pos]);
    // alaput, alapkor, ut2, pos
    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();
        }
    }
}
 
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;
    }
    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) {
        return false;
    } else {
        ans=valt(ans);
        assert(ans.size()>0);
        return ans;
        //return true;
    }
    /*if (N > 2) {
        return vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
    }
    return false;*/
}
/*
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 ans=find_journey(nn, mm, aa, bb);
    cout << "sikerult: " << ans << "\n";
    return 0;
}
*/
/*
2 3
0 1
1 0
1 0
*/

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