Submission #1236477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236477		Ghulam_Junaid	Thousands Islands (IOI22_islands)	C++20	11.90 / 100	28 ms	17224 KiB

islands

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

const int N = 2e5 + 10;
int n, m, out_deg[N], dead[N];
vector<int> g[N], rev[N], U, V;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> uu, vector<int> vv) {
    V = vv, U = uu;
    n = N, m = M;
    for (int i = 0; i < m; i ++){
        g[U[i]].push_back(i);
        out_deg[U[i]]++;
        rev[V[i]].push_back(i);
    }

    queue<int> q;
    for (int i = 0; i < n; i ++)
        if (!out_deg[i])
            q.push(i);

    while (!q.empty()){
        int v = q.front();
        q.pop();
        dead[v] = 1;

        for (int e : rev[v]){
            int u = U[e];
            out_deg[u]--;
            if (!out_deg[u])
                q.push(u);
        }
    }
    if (dead[0]) return false;

    for (int v = 0; v < n; v ++){
        vector<int> adj;
        for (int e : g[v]){
            int u = V[e];
            if (!dead[u] and !dead[v]) adj.push_back(e);
        }
        g[v] = adj;

        adj.clear();
        for (int e : rev[v]){
            int u = U[e];
            if (!dead[u] and !dead[v]) adj.push_back(e);
        }
        rev[v] = adj;
    }

    vector<int> start_path;
    
    int start = 0;
    int ite = 0;
    while (out_deg[start] == 1){
        ite++;
        
        dead[start] = 1;
        out_deg[start] = 0;
        for (int e : rev[start]){
            int u = U[e];
            out_deg[u]--;
            if (out_deg[u] == 0)
                dead[u] = 1;
        }

        int e = g[start][0];
        for (int i = 0; i < g[start].size(); i ++)
            if (!dead[V[g[start][i]]])
                e = g[start][i];
        int nxt = V[g[start][e]];

        start_path.push_back(e);
        start = nxt;

        if (dead[start]) break;
    }

    if (out_deg[start] <= 1) return false;
    return true;
}

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