Submission #1158309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158309		Math4Life2020	수천개의 섬 (IOI22_islands)	C++20	14.10 / 100	282 ms	32704 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

const ll Nm = 1e5+5;

variant<bool,vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    if (N==2) {
        vector<ll> vf,vr;
        for (ll i=0;i<M;i++) {
            if (U[i]==0) {
                vf.push_back(i);
            } else {
                vr.push_back(i);
            }
        }
        if (vf.size()<=1 || vr.size()<=0) {
            return false;
        } else {
            return (vector<ll>) {vf[0],vr[0],vf[1],vf[0],vr[0],vf[1]};
        }
    }
    map<pii,ll> mcnt; //map to count
    map<pii,vector<ll>> mvec;
    for (ll i=0;i<M;i++) {
        if (mcnt.find({U[i],V[i]})==mcnt.end()) {
            mcnt[{U[i],V[i]}]=0;
        }
        mcnt[{U[i],V[i]}]++;
        mvec[{U[i],V[i]}].push_back(i);
    }
    bool f1 = 1, f2 = 1;
    for (auto A0: mcnt) {
        pii p0 = (A0).first;
        if (mcnt[p0]%2!=0) {
            f2 = 0;
        }
        if (mcnt[p0]!=mcnt[{p0.second,p0.first}]) {
            f1 = 0;
        }
    }
    if (f1) { //easier case
        vector<array<ll,3>> adj[N];
        for (auto A0: mcnt) {
            pii p0 = A0.first;
            if (p0.first>p0.second) {
                continue;
            }
            vector<ll> v1 = mvec[p0];
            vector<ll> v2 = mvec[{p0.second,p0.first}];
            for (ll T=0;T<v1.size();T++) {
                adj[p0.first].push_back({p0.second,v1[T],v2[T]});
                adj[p0.second].push_back({p0.first,v1[T],v2[T]});
            }
        }
        vector<ll> vcur;
        if (adj[0].size()>=2) {
            return (vector<ll>){adj[0][0][1],adj[0][0][2],adj[0][1][1],adj[0][1][2],adj[0][0][1],adj[0][0][2],adj[0][1][1],adj[0][1][2]};
        } else if (adj[0].size()==0) {
            return false;
        }
        ll xc = adj[0][0][0];
        ll xp = 0;
        while(1) {
            if (adj[xc].size()>=3) {
                ll i1,i2;
                if (adj[xc][0][0]==xp) {
                    i1 = 1; i2 = 2;
                } else if (adj[xc][1][0]==xp) {
                    i1 = 0; i2 = 2;
                } else {
                    i1 = 0; i2 = 1;
                }
                vector<ll> vans = vcur;
                vans.push_back(adj[xc][i1][1]);
                vans.push_back(adj[xc][i1][2]);
                vans.push_back(adj[xc][i2][1]);
                vans.push_back(adj[xc][i2][2]);
                vans.push_back(adj[xc][i1][1]);
                vans.push_back(adj[xc][i1][2]);
                vans.push_back(adj[xc][i2][1]);
                vans.push_back(adj[xc][i2][2]);
                for (ll T=(vcur.size()-1);T>=0;T--) {
                    vans.push_back(vcur[T]);
                }
                return vans;
            } else if (adj[xc].size()==2) {
                if (adj[xc][0][0]==xp) {
                    xp = xc; xc = adj[xc][1][0];
                } else {
                    xp = xc; xc = adj[xc][0][0];
                }
            } else {
                return false;
            }
        } 
    }
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:99:1: warning: control reaches end of non-void function [-Wreturn-type]
   99 | }
      | ^

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