제출 #1158321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158321		Math4Life2020	수천개의 섬 (IOI22_islands)	C++20	31 / 100	285 ms	32840 KiB

islands

#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,v2[T],v1[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][2],adj[0][0][1],adj[0][1][2],adj[0][1][1]};
        } else if (adj[0].size()==0) {
            return false;
        }
        vcur.push_back(adj[0][0][1]);
        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][2]);
                vans.push_back(adj[xc][i1][1]);
                vans.push_back(adj[xc][i2][2]);
                vans.push_back(adj[xc][i2][1]);
                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) {
                    vcur.push_back(adj[xc][1][1]);
                    xp = xc; xc = adj[xc][1][0];
                } else {
                    vcur.push_back(adj[xc][0][1]);
                    xp = xc; xc = adj[xc][0][0];
                }
            } else {
                return false;
            }
        } 
    }
}

컴파일 시 표준 에러 (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:101:1: warning: control reaches end of non-void function [-Wreturn-type]
  101 | }
      | ^

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