Submission #1024760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024760		vjudge1	Thousands Islands (IOI22_islands)	C++17	55 / 100	81 ms	14572 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#include <variant>

#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
#define in insert
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()

using namespace std;

const int MAX=1e3+10;

vector<pii> g[MAX];
int use[MAX];
int pr[MAX];
int d[MAX];
int cycle;

void dfs(int v,int p=-1){
	pr[v]=p;
	use[v]=1;
	int cnt=0;
	for(auto to:g[v]){
		if(pr[v]!=-1&&to.S==(pr[v]%2==0?pr[v]+1:pr[v]-1))continue;
		cnt++;
		if(use[to.F])continue;
		d[to.F]=d[v]+1;
		dfs(to.F,to.S);
	}
	if(cnt>=2){
		cycle=v;
	}
}

int rev(int x){
	return (x%2==0?x+1:x-1);
}

void dfs1(int v,int p=-1){
	pr[v]=p;
	use[v]=1;
	for(auto to:g[v]){
		if(use[to.F]==1){
			cycle=to.S;
		}
		else if(!use[to.F]){
			d[to.F]=d[v]+1;
			dfs1(to.F,to.S);
		}
	}
    use[v]=2;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U,vector<int> V){
	// return true;
	cycle=-1;
    map<pii,int> mp;
    bool sub=1;
	for(int i=0;i<M;i++){
        mp[{U[i],V[i]}]=i;
		g[U[i]].pb({V[i],i});
        if(i%2==0&&i+1<M){
            sub&=(U[i]==V[i+1]);
            sub&=(V[i]==U[i+1]);
        }
	}
	if(N==2){
		if(sz(g[0])>=2&&sz(g[1])>=1){
			vector<int> vec={g[0][0].S,g[1][0].S,g[0][1].S,g[0][0].S,g[1][0].S,g[0][1].S};
			return vec;
		}return false;
	}
    if(sz(mp)==M&&sz(g[0])>=2){
        int a=g[0][0].F,b=g[0][1].F;
        vector<int> vec={mp[{0,a}],mp[{a,0}],mp[{0,b}],mp[{b,0}],mp[{a,0}],mp[{0,a}],mp[{b,0}],mp[{0,b}]};
        return vec;
    }
    if(sub){
        dfs(0);
        if(cycle==-1)return false;
        vector<int> ans;
        vector<int> c;
        int X=-1,Y=-1;
        for(auto to:g[cycle]){
            if(to.S==rev(pr[cycle]))continue;
            if(X==-1)X=to.S;
            else Y=to.S;
        }
        while(cycle!=0){
            c.pb(pr[cycle]);
            cycle=U[pr[cycle]];
        }
        reverse(all(c));
        for(int x:c)ans.pb(x);

        {
            ans.pb(X);
            ans.pb(rev(X));
            ans.pb(Y);
            ans.pb(rev(Y));
            ans.pb(rev(X));
            ans.pb(X);
            ans.pb(rev(Y));
            ans.pb(Y);
        }

        reverse(all(c));
        for(int x:c)ans.pb(x);
        return ans; 
    }

    dfs1(0);
    if(cycle==-1)return false;
    // cerr<<"OK\n";
    // return false;
    int st=U[cycle];
    vector<int> a;
    while(st!=V[cycle]){
        a.pb(pr[st]);
        st=U[pr[st]];
    }
    reverse(all(a));
    a.pb(cycle);
    vector<int> c;
    vector<int> ans;
    while(st!=0){
        c.pb(pr[st]);
        st=U[pr[st]];
    }
    reverse(all(c));
    for(int x:c)ans.pb(x);

    for(int x:a)ans.pb(x);
    for(int x:a)ans.pb(rev(x));
    reverse(all(a));
    for(int x:a)ans.pb(x);
    for(int x:a)ans.pb(rev(x));

    reverse(all(c));
    for(int x:c)ans.pb(x);
    return ans;
}

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