Submission #1070558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070558		Mihailo	Thousands Islands (IOI22_islands)	C++17	35 / 100	203 ms	46676 KiB

islands

#include <bits/stdc++.h>
#include <variant>
#include <vector>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000002022ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;

multiset<ll> to[100100], from[100100];
vector<ll> braket;
ll root;
bool dead[100100];

void erase(ll cur) {
    if(dead[cur]) return;
    vector<ll> kill;
    for(auto i:to[cur]) {
        from[i].erase(from[i].find(cur));
        if(i!=root&&from[i].empty()) kill.pb(i);
    }
    for(auto i:from[cur]) {
        to[i].erase(to[i].find(cur));
        if(to[i].empty()) kill.pb(i);
    }
    dead[cur]=true;
    for(auto i:kill) erase(i);
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    variant<bool, vector<int>> v;
    for(int i=0; i<M; i++) {
        to[U[i]].insert(V[i]);
        from[V[i]].insert(U[i]);
    }
    for(int i=0; i<N; i++) {
        if(to[i].empty()||(i!=root&&from[i].empty())) erase(i);
    }
    if(dead[root]) {
        v=false;
        return v;
    }
    while(to[root].size()==1) {
        ll t=root;
        braket.pb(t);
        root=*to[root].begin();
        erase(t);
        if(dead[root]) {
            v=false;
            return v;
        }
    }
    v=true;
    return v;
}

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