제출 #774459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774459		GusterGoose27	수천개의 섬 (IOI22_islands)	C++17	11.90 / 100	38 ms	15032 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
vector<pii> edges[MAXN];
vector<pii> redges[MAXN];
bool dead[MAXN];
int indeg[MAXN];
int outdeg[MAXN];
pii par[MAXN];
pii par2[MAXN];
pii edge_list[MAXN];
int n, m;
vector<int> path[2];
int cyc_node;
bool fin[MAXN];
bool vis[MAXN];

void prune(int i) {
    dead[i] = 1;
    if (indeg[i] == 0) {
        return;
    }
    for (pii e: redges[i]) {
        if (dead[e.first]) continue;
        outdeg[e.first]--;
        if (outdeg[e.first] == 0) prune(e.first);
    }
    indeg[i] = 0;
}

void make_path(int cur, vector<int> &cpath, bool spec = 1) {
    if (spec == 1 && par2[cur].first != -1) {
        make_path(par2[cur].first, cpath, 0);
        cpath.push_back(par2[cur].second);
    }
    if (cur == 0) return;
    make_path(par[cur].first, cpath, 0);
    cpath.push_back(par[cur].second);
}

bool dfs(int cur) {
    vis[cur] = 1;
    for (pii e: edges[cur]) {
        if (dead[e.first]) continue;
        if (fin[e.first]) { // do things
            make_path(e.first, path[0]);
            make_path(cur, path[1]);
            path[1].push_back(e.second);
            cyc_node = e.first;
            return 1;
        }
        if (vis[e.first]) {
            if (outdeg[e.first] > 1) return 1;
            // par2[e.first] = pii(cur, e.second);
            continue;
        }
        par[e.first] = pii(cur, e.second);
        if (dfs(e.first)) return 1;
    }
    fin[cur] = 1;
    return 0;
}

pii nxt[MAXN];
pii prv[MAXN];
int pinch;

bool make_cyc(int s) {
    vis[s] = 1;
    for (pii e: edges[s]) {
        if (dead[e.first]) continue;
        if (vis[e.first]) {
            nxt[s] = e;
            pinch = e.first;
            prv[e.first] = pii(s, e.second);
            return 1;
        }
        if (make_cyc(e.first)) {
            if (e.first != pinch && prv[nxt[e.first].first].first == e.first) prv[e.first] = pii(s, e.second);
            nxt[s] = e;
            return 1;
        }
    }
    return 0;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        edges[U[i]].push_back(pii(V[i], i));
        redges[V[i]].push_back(pii(U[i], i));
        edge_list[i] = pii(U[i], V[i]);
        indeg[V[i]]++;
        outdeg[U[i]]++;
    }
    for (int i = 0; i < n; i++) {
        if (!dead[i] && outdeg[i] == 0) prune(i);
    }
    if (dead[0]) return false;
    par[0] = pii(-1, -1);
    fill(par2, par2+n, pii(-1, -1));
    if (!dfs(0)) return false;
    return vector<int>({});
    int t = 0;
    while (t < path[0].size() && t < path[1].size() && path[0][t] == path[1][t]) {
        t++;
    }
    assert(t < path[0].size() && t < path[1].size());
    fill(nxt, nxt+n, pii(-1, -1));
    fill(prv, prv+n, pii(-1, -1));
    fill(vis, vis+n, 0);
    bool b = make_cyc(cyc_node); assert(b); // goal is to evert the pinch cycle
    vector<int> res;
    for (int i = 0; i < t; i++) res.push_back(path[0][i]);

    for (int _ = 0; _ < 2; _++) { // special case 0 is on cycle or smth
        int j = t;
        while (j < path[_].size() && nxt[edge_list[path[_][j]].first].first == -1) {
            res.push_back(path[_][j]);
            j++;
        }
        vector<int> to_rev;
        int cur_node = (j == path[_].size() ? edge_list[path[_].back()].second : edge_list[path[_][j]].first);
        while (prv[cur_node].first == -1) {
            to_rev.push_back(nxt[cur_node].second);
            res.push_back(nxt[cur_node].second);
            cur_node = nxt[cur_node].first;
        }
        int cur = cur_node;
        do {
            if (_ == 0) {
                res.push_back(nxt[cur].second);
                cur = nxt[cur].first;
            }
            else {
                res.push_back(prv[cur].second);
                cur = prv[cur].first;
            }
        } while (cur != cur_node);
        for (int i = to_rev.size()-1; i >= 0; i--) res.push_back(to_rev[i]);
        for (int i = j-1; i >= t; i--) res.push_back(path[_][i]);
    }
    for (int i = t-1; i >= 0; t--) res.push_back(path[0][i]);
    return res;
}

컴파일 시 표준 에러 (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:112:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     while (t < path[0].size() && t < path[1].size() && path[0][t] == path[1][t]) {
      |            ~~^~~~~~~~~~~~~~~~
islands.cpp:112:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     while (t < path[0].size() && t < path[1].size() && path[0][t] == path[1][t]) {
      |                                  ~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from islands.cpp:3:
islands.cpp:115:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     assert(t < path[0].size() && t < path[1].size());
      |            ~~^~~~~~~~~~~~~~~~
islands.cpp:115:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     assert(t < path[0].size() && t < path[1].size());
      |                                  ~~^~~~~~~~~~~~~~~~
islands.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         while (j < path[_].size() && nxt[edge_list[path[_][j]].first].first == -1) {
      |                ~~^~~~~~~~~~~~~~~~
islands.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         int cur_node = (j == path[_].size() ? edge_list[path[_].back()].second : edge_list[path[_][j]].first);
      |                         ~~^~~~~~~~~~~~~~~~~

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