제출 #648947

#제출 시각아이디문제언어결과실행 시간메모리
648947blue수천개의 섬 (IOI22_islands)C++17
35 / 100
131 ms17912 KiB
#include "islands.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using pii = pair<int, int>; using vpii = vector<pii>; #define sz(x) int(x.size()) const int mx = 100'000; vpii edge[mx]; vpii revedge[mx]; int N, M; queue<int> tbv; int src = 0; vi pushed(mx, 0); vi killed(mx, 0); vi outdeg(mx, 0); vi incedge(mx, -1); void gettime() { for(int j = 1; j <= 500'000; j++) cerr << "hello world\n"; } variant<bool, vi> find_journey(int N_, int M_, vi U, vi V) { N = N_; M = M_; for(int j = 0; j < M; j++) { edge[U[j]].push_back({V[j], j}); revedge[V[j]].push_back({U[j], j}); outdeg[U[j]]++; } for(int i = 0; i < N; i++) { if(outdeg[i] == 0) { pushed[i] = 1; tbv.push(i); } } if(pushed[src]) { // gettime(); return false; } vi originlist; // cerr << sz(tbv) << " ! \n"; // cerr << "outdeg 1 = " << outdeg[1] << '\n'; while(1) { if(!tbv.empty()) { int u = tbv.front(); tbv.pop(); killed[u] = 1; for(pii vp : revedge[u]) { int v = vp.first; // cerr << "remove out edge from " << v << " to del node = " << u << ", edge ind = " << vp.second << '\n'; outdeg[v]--; // cerr << "outdeg " << v << " = " << outdeg[v] << '\n'; if(outdeg[v] == 0) { pushed[v] = 1; if(v == src) { // gettime(); return false; } tbv.push(v); // cerr << "push " << v << " to killing queue\n"; } } } else if(outdeg[src] == 1) { int newsrc; for(pii vp : edge[src]) { if(!pushed[vp.first]) { newsrc = vp.first; incedge[newsrc] = vp.second; break; } } pushed[src] = 1; killed[src] = 1; originlist.push_back(src); for(pii vp : revedge[src]) { int v = vp.first; if(vp.second == incedge[src]) continue; // cerr << "remove out edge from " << v << " to src = " << src << ", edge ind = " << vp.second << '\n'; outdeg[v]--; // cerr << "outdeg " << v << " = " << outdeg[v] << '\n'; if(outdeg[v] == 0) { pushed[v] = 1; if(pushed[newsrc]) return false; tbv.push(v); // cerr << "push " << v << " to killing queue\n"; } } // cerr << src << " -> " << newsrc << '\n'; src = newsrc; } else { break; } } // for(int j = 1; j <= 500'000; j++) // cerr << "hello world\n"; return true; }

컴파일 시 표준 에러 (stderr) 메시지

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, vi, vi)':
islands.cpp:124:22: warning: 'newsrc' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |      if(pushed[newsrc])
      |                      ^
#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...