Submission #1074444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074444		Zicrus	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	40 ms	11368 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;
unordered_multiset<ll> has;
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]) {
        ll hash = ((ll)min(cur, e.second) << 31) | max(cur, e.second);
        if (!has.count(hash)) continue;
        if (twin[e.first] == parE) continue;
        if (poss(e.second, e.first)) {
            revPath.push_back(e.first);
            return true;
        }
        cnt++;
        if (cnt <= 2) {
            edges.push_back(e.first);
            edges.push_back(twin[e.first]);
        }
    }
    if (cnt >= 2) {
        endTrick = edges;
    }
    return cnt >= 2;
}

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]});
        if (U[i] < V[i]) {
            ll hash = ((ll)U[i] << 31) | V[i];
            has.insert(hash);
        }
        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 < revPath.size(); i++) {
        res.push_back(twin[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: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: 1.75 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45