Submission #1159433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159433		Samuraj	수천개의 섬 (IOI22_islands)	C++20	10.85 / 100	22 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 ini(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;
        min_ind[x.st] = min(min_ind[x.st],min_ind[v]);
        ini(x.st);
        max_ind[v] = max(max_ind[v],max_ind[x.st]); //to powinno byc pozniej!
    }
}

bool check_ans(int v){
    //cerr << "v: " << v << " min_ind: " << min_ind[v] << '\n';
    bool ans = 0;
    int ile_c = 0;
    if(max_ind[v] >= min_ind[v]) ans = 1; //imo check wystarczy!
    for(auto x:g[v]){
        if(!odw[x.st]) continue; //moze sie przyda!
        if(drzewowa[x.nd]){
            ans |= check_ans(x.st);
            if(max_ind[x.st] >= h[v]) ile_c++;
        }
    }
    //cout << "v: " << v << " ile_c: " << ile_c << '\n';
    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;
    }
    //stworzyc min i max
    set_h(0); //cerr << "set_h\n";
    rep(v,0,n-1){
        //cerr << "\nv: " << v << '\n';
        for(auto x:g[v]){
            //cout << "x: " << x.st << ' ' << x.nd << '\n';
            //cout << "drzewowa: " << drzewowa[x.nd] << " odw: " << odw[x.st] << '\n';
            if(drzewowa[x.nd] || !odw[x.st]) continue;
            //cout <<" ustawiamy\n";
            if(h[x.st] < h[v]) max_ind[v] = max(max_ind[v],h[x.st]);
            if(h[x.st] > h[v]) min_ind[x.st] = min(min_ind[x.st],h[v]);
        }
    }
    ini(0); //cerr << "set_cykl\n";
    //debug
    //rep(v,0,n-1) cerr << "v: " << v << " min: " << min_ind[v] << " max: " << max_ind[v] << '\n';
    //bool ans = 0;
    bool ans = check_ans(0); //cerr << "ans: " << ans << '\n';
    if(!ans) return false;
    return true;
    //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