Submission #1074515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074515		Zicrus	Thousands Islands (IOI22_islands)	C++17	26 / 100	46 ms	9920 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"
using namespace std;

typedef long long ll;

int n, m;
vector<vector<pair<int, int>>> adj, revAdj; // edgeId, node
vector<bool> vst;
vector<int> twin;
vector<int> endTrick;
vector<int> revPath;

bool poss(int cur, int parE) {
    if (vst[cur]) return false;
    vst[cur] = true;
    int cnt = 0;
    vector<int> edges;
    for (auto &e : adj[cur]) {
        if (twin[e.first] == parE) continue;
        cnt++;
        if (cnt <= 2) {
            edges.push_back(e.first);
            edges.push_back(twin[e.first]);
        }
    }
    if (cnt >= 2) {
        endTrick = edges;
        return true;
    }
    for (auto &e : adj[cur]) {
        if (twin[e.first] == parE) continue;
        if (poss(e.second, e.first)) {
            revPath.push_back(e.first);
            return true;
        }
    }
    return false;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N; m = M;
    adj = vector<vector<pair<int, int>>>(n);
    unordered_map<ll, int> twinS;
    twin = vector<int>(m);
    for (int i = 0; i < m; i++) {
        adj[U[i]].push_back({i, V[i]});
        ll hash = ((ll)U[i] << 31) | V[i];
        ll revHash = ((ll)V[i] << 31) | U[i];
        if (twinS.count(revHash)) {
            twin[i] = twinS[revHash];
            twin[twin[i]] = i;
            twinS.erase(revHash);
        }
        else {
            twinS[hash] = i;
        }
    }
    vst = vector<bool>(n);
    if (!poss(0, -1)) {
        return false;
    }
    vector<int> res;
    for (int i = revPath.size()-1; i >= 0; i--) {
        res.push_back(revPath[i]);
    }
    for (int i = 0; i < endTrick.size(); i++) {
        res.push_back(endTrick[i]);
    }
    for (int i = 0; i < endTrick.size(); i++) {
        res.push_back(endTrick[i^1]);
    }
    for (int i = 0; i < revPath.size(); i++) {
        res.push_back(revPath[i]);
    }
    return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

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:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < endTrick.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
islands.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < endTrick.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
islands.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < revPath.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

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