Submission #1175298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175298		onlk97	Thousands Islands (IOI22_islands)	C++17	15.15 / 100	133 ms	34092 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

int n,m;
set <pair <int,int> > in[100010],out[100010];
vector <pair <int,int> > g[100010];
map <pair <int,int>,int> mp;
void reduce(){
    queue <int> q;
    for (int i=0; i<n; i++){
        if (out[i].empty()) q.push(i);
    }
    while (!q.empty()){
        int tp=q.front(); q.pop();
        for (auto i:in[tp]){
            out[i.first].erase({tp,i.second});
            if (out[i.first].empty()) q.push(i.first);
        }
        in[tp].clear();
    }
}
vector <int> prep;
int fol(int st){
    set <int> seen;
    seen.insert(st);
    while (out[st].size()==1){
        prep.push_back((*out[st].begin()).second);
        st=(*out[st].begin()).first;
        if (seen.find(st)!=seen.end()) return -1;
    }
    if (out[st].empty()) return -1;
    return st;
}
int visited[100010];
vector <int> vec;
bool found;
void dfs(int cur){
    visited[cur]=1;
    vec.push_back(cur);
    for (auto i:g[cur]){
        if (visited[i.first]==2) continue;
        if (!visited[i.first]){
            dfs(i.first);
            if (found) return;
            continue;
        }
        found=1;
        vec.push_back(i.first);
    }
    if (found) return;
    visited[cur]=2;
    vec.pop_back();
}
void find_cycle(int st){
    for (int i=0; i<n; i++) visited[i]=0;
    vec.clear(); found=0;
    dfs(st);
}
pair <vector <int>,vector <int> > getroute(){
    int idx;
    for (int i=0; i+1<vec.size(); i++) if (vec[i]==vec.back()){
        idx=i;
        break;
    }
    vector <int> path,cyc;
    for (int i=1; i<=idx; i++) path.push_back(mp[{vec[i-1],vec[i]}]);
    for (int i=idx+1; i<vec.size(); i++) cyc.push_back(mp[{vec[i-1],vec[i]}]);
    return {path,cyc};
}
bool intrs(vector <int> a,vector <int> b){
    set <int> sa;
    for (int i:a) sa.insert(i);
    for (int i:b) if (sa.find(i)!=sa.end()) return 1;
    return 0;
}
vector <int> ans;
void append(vector <int> v,bool rev){
    if (rev) reverse(v.begin(),v.end());
    for (int i:v) ans.push_back(i);
}
variant <bool,vector <int> > find_journey(int N,int M,vector <int> U,vector <int> V){
    n=N; m=M;
    for (int i=0; i<M; i++){
        out[U[i]].insert({V[i],i});
        in[V[i]].insert({U[i],i});
    }
    reduce();
    if (!out[0].size()) return false;
    int st=0;
    st=fol(st);
    if (st==-1) return false;
    for (int i:prep){
        out[U[i]].erase({V[i],i});
        in[V[i]].erase({U[i],i});
    }
    reduce();
    if (!out[st].size()) return false;
    for (int i=0; i<n; i++){
        while (out[i].size()>1+(i==st)) out[i].erase(--out[i].end());
    }
    for (int i=0; i<n; i++){
        for (auto j:out[i]){
            g[i].push_back(j);
            mp[{i,j.first}]=j.second;
        }
    }
    find_cycle(st);
    pair <vector <int>,vector <int> > p1=getroute();
    if (!p1.first.empty()) p1.first[0]=g[st][0].second;
    else p1.second[0]=g[st][0].second;
    reverse(g[st].begin(),g[st].end());
    find_cycle(st);
    pair <vector <int>,vector <int> > p2=getroute();
    append(prep,0);
    if (intrs(p1.second,p2.second)){
        append(p1.first,0);
        append(p1.second,0);
        append(p1.first,1);
        append(p2.first,0);
        append(p2.second,1);
        append(p2.first,1);
    } else {
        append(p1.first,0);
        append(p1.second,0);
        append(p1.first,1);
        append(p2.first,0);
        append(p2.second,0);
        append(p2.first,1);
        append(p1.first,0);
        append(p1.second,1);
        append(p1.first,1);
        append(p2.first,0);
        append(p2.second,1);
        append(p2.first,1);
    }
    append(prep,1);
    return ans;
}

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