Submission #1037568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037568		12345678	Thousands Islands (IOI22_islands)	C++17	22.75 / 100	21 ms	5332 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e3+5;
 
int ans, vs[nx], a, b, c,D;
pair<int, int> pa[nx];
vector<pair<int, int>> d[nx];
vector<int> res;

int adjust(int x)
{
    int tmp=1-x%2;
    return (x/2)*2+tmp;
}

void dfs(int u, int p)
{
    if (ans) return;
    vs[u]=1;
    //cout<<"dfs "<<u<<' '<<p<<'\n';
    if (!ans&&(int)d[u].size()-(u!=p)>=2) 
    {
        vector<int> tmp;
        int cur=u, cnt=0;
        while (cur!=0) tmp.push_back(pa[cur].second), cur=pa[cur].first;
        reverse(tmp.begin(), tmp.end());
        for (auto x:tmp) res.push_back(x);
        reverse(tmp.begin(), tmp.end());
        //cout<<"size "<<d[u].size()<<'\n';
        for (auto [x, idx]:d[u]) 
        {
            //cout<<"here "<<x<<' '<<idx<<'\n';
            if (x!=p&&cnt==0)
            {
                a=idx;
                b=adjust(a);
                cnt++;
            }
            else if (x!=p&&cnt==1)
            {
                c=idx;
                D=adjust(c);
                cnt++;
            }
        }
        //cout<<"debug "<<a<<' '<<b<<' '<<c<<' '<<D<<'\n';
        res.push_back(a);
        res.push_back(b);
        res.push_back(c);
        res.push_back(D);
        res.push_back(b);
        res.push_back(a);
        res.push_back(D);
        res.push_back(c);
        for (auto x:tmp) res.push_back(x);
        ans=1;
    }
    for (auto [v, idx]:d[u]) if (v!=p&&!vs[v]) pa[v]={u, idx}, dfs(v, u);
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    for (int i=0; i<M; i+=2) d[U[i]].push_back({V[i], i}), d[V[i]].push_back({U[i], i+1});
    //for (int i=0; i<N;i ++) cout<<"sz "<<i<<' '<<d[i].size()<<'\n';
    dfs(0, 0);
    if (ans) return res;
    return false;
}

/*
4 6
0 1
1 0
1 2
2 1
3 1
1 3

3 4
0 1
1 0
2 0
0 2
*/

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