Submission #1158967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158967		Samuraj	Thousands Islands (IOI22_islands)	C++20	10.85 / 100	23 ms	10056 KiB

islands

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

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const int max_n = 2e5+7;
const int INF = 1e9+7;

vector<pi> g[max_n];
bool drzewowa[max_n];

bool odw[max_n];
int h[max_n];
bool cykl[max_n]; //cykl nizej!
int min_ind[max_n]; //min h na ktorej sie rozdzielamy by dojsc do tego wierzcholka!
int max_ind[max_n]; //max h dla ktorej mamy krawedz wsteczną nad nami!

void set_h(int v){
    //cerr << "\nset_h, v: " << v << " h: " << h[v] << '\n';
    odw[v] = 1;
    for(auto x:g[v]){
        if(odw[x.st]) continue;
        drzewowa[x.nd] = 1;
        h[x.st] = h[v]+1;
        set_h(x.st);
    }
}

void set_ind(int v){
    //cerr << "\nset_cykl od v: " << v << '\n';
    for(auto x:g[v]){
        //cerr << "x.st: " << x.st << " nd: " << x.nd << '\n'; 
        if(!drzewowa[x.nd]) continue;
        set_ind(x.st);
        max_ind[v] = max(max_ind[v],max_ind[x.st]); //to powinno byc pozniej!
    }

    for(auto x:g[v]){
        if(drzewowa[x.nd]) continue;
        if(h[x.st] < h[v]){
            //cerr << "wsteczna\n";
            max_ind[v] = max(max_ind[v],h[x.st]);
        }       
        else{
            //cerr << "set_min\n";
            min_ind[x.st] = min(min_ind[x.st],h[v]);
        }
    }
}

bool check_ans(int v){
    //cerr << "v: " << v << " min_ind: " << min_ind[v] << '\n';
    bool ans = 0;
    int ile_c = 0;
    for(auto x:g[v]){
        if(drzewowa[x.nd]){
            min_ind[x.st] = min(min_ind[x.st],min_ind[v]);
            if(max_ind[x.st] >= h[v]) ile_c++;
            ans |= check_ans(x.st);
        }
        //krawedz wsteczna, warunek czy dwie sciezki na jeden cykl!
        if(h[x.st] < h[v] && min_ind[v] <= h[x.st]) ans = 1;
    }
    if(ile_c >= 2) ans = 1;
    return ans;
}

variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
    rep(i,0,m-1) g[U[i]].pb({V[i],i});
    rep(i,0,n-1){
        min_ind[i] = INF; max_ind[i] = -1;
    }
    set_h(0); //cerr << "set_h\n";
    set_ind(0); //cerr << "set_cykl\n";
    //bool ans = 0;
    bool ans = check_ans(0); //cerr << "ans: " << ans << '\n';
    if(!ans) return false;

    vi vec; rep(i,0,n-1) vec.pb(i); //cokolwiek
    return vec;
}

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