제출 #1074444

#제출 시각아이디문제언어결과실행 시간메모리
1074444Zicrus수천개의 섬 (IOI22_islands)C++17
9.10 / 100
40 ms11368 KiB
#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

컴파일 시 표준 에러 (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++) {
      |                     ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...