Submission #824308

#	Time	Username	Problem	Language	Result	Execution time	Memory
824308		vjudge1	Thousands Islands (IOI22_islands)	C++17	22.75 / 100	32 ms	10896 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
struct edge {
    int to, ind, rev;
};
vector<edge> adj[200100];
int ind[1000][1000];
bool vis[1000];
vector<int> ans;
bool dfs(int n, int p) {
    if(vis[n]) return 0;
    vis[n] = 1;
    if(adj[n].size()>2-!(p+1)) {
        int a=-1, b, c=-1, d;
        for(auto i: adj[n])
            if(i.to!=p) {
                if(a<0)
                    a = i.ind, b = i.rev;
                else if(c<0)
                    c = i.ind, d = i.rev;
            }
        ans.push_back(a);
        ans.push_back(b);
        ans.push_back(c);
        ans.push_back(d);
        ans.push_back(b);
        ans.push_back(a);
        ans.push_back(d);
        ans.push_back(c);
        return 1;
    }
    for(auto i: adj[n]) {
        ans.push_back(i.ind);
        if(dfs(i.to, n)) {
            ans.push_back(i.ind);
            return 1;
        }
        ans.pop_back();
    }
    return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    for(int i = 0; i < M; i++)
        adj[U[i]].push_back({V[i], i, i/2*4-i+1});
    if(dfs(0,-1)) {
        return ans;
    } else {
        return false;
    }
}

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