Submission #1058215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058215		hirayuu_oj	Thousands Islands (IOI22_islands)	C++17	10 / 100	60 ms	31168 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    if(N==2) {
        vector<vector<int>> cnt(2);
        rep(i,M)cnt[U[i]].emplace_back(i);
        if(cnt[0].size()>=2&&cnt[1].size()>=1) {
            return vector<int>{cnt[0][0],cnt[1][0],cnt[0][1],cnt[0][0],cnt[1][0],cnt[0][1]};
        }
        else {
            return false;
        }
    }
    bool subtask2=true;
    if(N>400)subtask2=false;
    array<array<vector<int>,1000>,1000> gr;
    rep(i,M) {
        if(gr[U[i]][V[i]].size()!=0)subtask2=false;
        gr[U[i]][V[i]].emplace_back(i);
    }
    if(M!=N*(N-1))subtask2=false;
    if(subtask2) {
        vector<int> ans;
        rep(i,N) {
            ans.emplace_back(gr[i][(i+1)%N][0]);
        }
        rep(i,N) {
            ans.emplace_back(gr[(N-i)%N][N-i-1][0]);
        }
        rep(i,N) {
            ans.emplace_back(gr[N-i-1][(N-i)%N][0]);
        }
        rep(i,N) {
            ans.emplace_back(gr[(i+1)%N][i][0]);
        }
        return ans;
    }
    else {
        vector<int> cnt(N,0);
        rep(i,N) {
            rep(j,N) {
                if(gr[i][j].size()>=2)return true;
                if(gr[i][j].size())cnt[i]++;
            }
        }
        stack<int> vis;
        vis.push(0);
        vector<int> can(N,0);
        can[0]=1;
        while(!vis.empty()) {
            int pos=vis.top();
            vis.pop();
            rep(i,N) {
                if(gr[pos][i].size()) {
                    if(can[i]==0) {
                        can[i]=1;
                        vis.push(i);
                    }
                }
            }
        }
        if(cnt[0]>=2)return true;
        int mx=0;
        for(int i:cnt){
            if(can[i]==1)mx=max(mx,cnt[i]);
        }
        if(mx>=3)return true;
        return false;
    }
    return false;
}

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