Submission #1235863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235863		mariza	Thousands Islands (IOI22_islands)	C++20	3.50 / 100	26 ms	16064 KiB

islands

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

typedef long long ll;
const ll N=1e5;

vector<ll> g[N], rg[N];

vector<ll> s;
bool vis[N]={};
void dfs1(ll curr){
    if(vis[curr]) return;
    vis[curr]=1;

    for(auto nxt:g[curr]){
        dfs1(nxt);
    }
    s.push_back(curr);
}

ll scc[N], sz[N];
void dfs2(ll curr, ll x){
    if(scc[curr]!=-1) return;
    scc[curr]=x;
    sz[x]++;

    for(auto nxt:rg[curr]){
        dfs2(nxt,x);
    }
}

vector<ll> dag[N+1];
ll c[N+1]={};
void dfs3(ll curr){
    if(c[curr]!=-1) return;
    c[curr]=0;
    for(auto nxt:dag[curr]){
        dfs3(nxt);
        c[curr]+=c[nxt];
    }
}

variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v) {
    for(ll i=0; i<m; i++){
        g[u[i]].push_back(v[i]);
        rg[v[i]].push_back(u[i]);
    }

    for(ll i=0; i<n; i++){
        dfs1(i);
        scc[i]=-1;
    }

    reverse(s.begin(),s.end());
    for(auto i:s){
        // cout<<i<<endl;
        dfs2(i,i);
    }

    for(ll i=0; i<m; i++){
        if(scc[u[i]]!=scc[v[i]] && u[i]!=0) dag[scc[v[i]]].push_back(scc[u[i]]);
    }
    for(ll i=0; i<m; i++){
        if(u[i]==0) dag[scc[v[i]]].push_back(n);
    }

    // for(ll i=0; i<n; i++){
    //     cout<<scc[i]<<" ";
    // }
    // cout<<endl;

    for(ll i=0; i<n; i++){
        c[i]=-1;
    }
    c[n]=1;

    bool ans=0;
    for(ll i=0; i<n; i++){
        dfs3(i);
        // cout<<sz[i]<<" "<<c[i]<<endl;
        if(sz[i]>1 && c[i]>=2) ans=1;
    }
    return ans;
}

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