Submission #720829

#	Time	Username	Problem	Language	Result	Execution time	Memory
720829		lam	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	36 ms	6752 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 2010;
const int maxm = 3e5+10;
int n,m;
bool ban[maxm];
bool vis[maxn];
bool check = 1;
vector <int> path;
vector <ii> adj[maxn];
int l[maxn],t[maxn],cnt;
int bridge;

void dfs(int x, int goal)
{
    vis[x]=1;
    if (x==goal)
    {
        check=1;
        return;
    }
    for (ii i:adj[x])
    {
        if (ban[i.ss]||vis[i.ff]) continue;
        path.push_back(i.ss);
        dfs(i.ff,goal);
        if (check) return;
        path.pop_back();
    }
}

void dfs2(int x, int p)
{
    l[x]=t[x]=++cnt;
    for (ii i:adj[x])
    {
        if (p!=-1&&(i.ss/2)==(p/2)) continue;
        if (t[i.ff]==0)
        {
            dfs2(i.ff,i.ss);
            l[x]=min(l[x],l[i.ff]);
            if (l[i.ff] != t[i.ff])
            {
                bridge = i.ss;
            }
        }
        else l[x]=min(l[x],t[i.ff]);
    }
}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
    n=N; m=M;
    for (int i=0; i<n; i++) adj[i].clear();
    fill_n(ban,m+1,0);
    path.clear();
    for (int i=0; i<m; i++)
    {
        int u=U[i]; int v=V[i];
        adj[u].push_back({v,i});
    }
    cnt=0;
    fill_n(l,n,0);
    fill_n(t,n,0);
    bridge = -1;
    dfs2(0,-1);
    if (bridge==-1) return false; //vector <int>({-1});
    fill_n(vis,n,0);
    int idx = (bridge/2)*2;
    ban[idx] = ban[idx+1] = 1;
    path.clear();
    check=0;
    dfs(0,U[idx]);
    vector <int> ans;
    for (int i:path) ans.push_back(i);
    ans.push_back(idx); ans.push_back(idx+1);
    reverse(path.begin(),path.end());
    for (int i:path) ans.push_back(i);
    path.clear();
    fill_n(vis,n,0);
    check=0;
    dfs(0,V[idx]);
    for (int i:path) ans.push_back(i);
    ans.push_back(idx); ans.push_back(idx+1);
    reverse(path.begin(),path.end());
    for (int i:path) ans.push_back(i);
    return ans;
}

//signed main()
//{
//    int n,m; cin>>n>>m;
//    vector <int> U,V;
//    for (int i=0; i<m; i++)
//    {
//        int u,v; cin>>u>>v;
//        U.push_back(u);
//        V.push_back(v);
//    }
//    vector <int> ans = find_journey(n,m,U,V);
//    for (int i:ans) cout<<i<<' '; cout<<endl;
//}
/**
6 12
1 0
0 1
2 0
0 2
2 5
5 2
0 3
3 0
4 2
2 4
4 2
2 4

**/

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