제출 #1078999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078999		jer033	수천개의 섬 (IOI22_islands)	C++17	24 / 100	28 ms	7860 KiB

islands

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

vector<int> generate_cycle(int N, vector<vector<pii>> (&edges), int start)
{
    //This function returns a cycle containing start, or reports that none exist
    vector<int> parent(N, -2);
    vector<int> parent_canoe(N, -2);
    queue<int> visitlist;

    parent[start] = -1;
    visitlist.push(start);
    while (!visitlist.empty())
    {
        int x = visitlist.front();
        visitlist.pop();
        for (pii neigh: edges[x])
        {
            int adj = neigh.first;
            int can = neigh.second;
            if (parent[adj]==-2)
            {
                parent[adj] = x;
                parent_canoe[adj] = can;
                visitlist.push(adj);
            }
            if (adj == start)
            {
                //create the cycle
                int curr = x;
                vector<int> cycle;
                cycle.push_back(can);
                while (curr!=start)
                {
                    cycle.push_back(parent_canoe[curr]);
                    curr = parent[curr];
                }
                //this cycle is actually reversed, so let's reverse it!
                int k = cycle.size();
                vector<int> real_cycle(k);
                for (int i=0; i<k; i++)
                    real_cycle[i] = cycle[k-1-i];
                
                return real_cycle;
            }
        }
    }

    return {};
}

bool journey_exists = 0;

vector<int> journey(int N, vector<vector<pii>> (&edges), vector<bool> (&in_cycle))
{
    vector<int> parent(N, -2);
    vector<int> parent_canoe(N, -2);
    queue<int> visitlist;

    parent[0] = -1;
    visitlist.push(0);
    while (!visitlist.empty())
    {
        int x = visitlist.front();
        visitlist.pop();
        if (in_cycle[x])
        {
            vector<int> cycle = generate_cycle(N, edges, x);
            int curr = x;
            vector<int> pre;
            while (curr!=0)
            {
                pre.push_back(parent_canoe[curr]);
                curr = parent[curr];
            }
            int k = pre.size();
            vector<int> real_pre(k);
            for (int i=0; i<k; i++)
                real_pre[i] = pre[k-1-i];
            
            int kc = cycle.size();

            vector<int> journey;
            for (int i=0; i<k; i++)
                journey.push_back(real_pre[i]);
            
            for (int i=0; i<kc; i++)
                journey.push_back(cycle[i]);
            for (int i=0; i<kc; i++)
                journey.push_back(cycle[i]+1);
            for (int i=0; i<kc; i++)
                journey.push_back(cycle[kc-i-1]);
            for (int i=0; i<kc; i++)
                journey.push_back(cycle[kc-i-1]+1);

            for (int i=0; i<k; i++)
                journey.push_back(pre[i]);
            
            journey_exists = 1;

            return journey;

        }
        for (pii neigh: edges[x])
        {
            int adj = neigh.first;
            int can = neigh.second;
            if (parent[adj]==-2)
            {
                parent[adj] = x;
                parent_canoe[adj] = can;
                visitlist.push(adj);
            }
        }
    }
    return {};
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    journey_exists = 0;
    vector<vector<pii>> edges(N);
    vector<int> out_deg(N, 0);
    vector<int> in_deg(N, 0);
    vector<vector<int>> edges_out(N);
    vector<vector<int>> edges_in(N);
    for (int i=0; i<M; i+=2)
    {
        int u = U[i];
        int v = V[i];
        edges[u].push_back({v, i});
        out_deg[u]++;
        in_deg[v]++;
        edges_out[u].push_back(v);
        edges_in[v].push_back(u);
    }
 
    //clear all nodes that don't have anything going into it
    queue<int> work;
    for (int i=0; i<N; i++)
        if (in_deg[i] == 0)
            work.push(i);
    
    while (!work.empty())
    {
        int x = work.front();
        work.pop();
        for (int y: edges_out[x])
        {
            out_deg[x]--;
            in_deg[y]--;
            if (in_deg[y] == 0)
                work.push(y);
        }
    }

    //clear all nodes that don't have anything going out of it
    for (int i=0; i<N; i++)
        if (out_deg[i] == 0)
            work.push(i);
    
    while (!work.empty())
    {
        int x = work.front();
        work.pop();
        for (int y: edges_in[x])
        {
            in_deg[x]--;
            out_deg[y]--;
            if (out_deg[y] == 0)
                work.push(y);
        }
    }

    //cout << "nakarating po dito\n";
    vector<bool> in_cycle(N, 0);
    for (int i=0; i<N; i++)
        if ((out_deg[i]>0) and (in_deg[i]>0))
            in_cycle[i] = 1;

    vector<int> sagot = journey(N, edges, in_cycle);
    if (journey_exists == 0)
        return journey_exists;
    return sagot;
}

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