제출 #830750

#제출 시각아이디문제언어결과실행 시간메모리
830750FatihSolak수천개의 섬 (IOI22_islands)C++17
0 / 100
182 ms31068 KiB
#include "islands.h" #include <bits/stdc++.h> #define N 100005 using namespace std; vector<pair<int,pair<int,int>>> adj[N]; map<int,vector<int>> mp[N]; int par[N]; int par2[N]; int vis[N]; vector<int> ans; bool ok = 0; void dfs2(int v,int pr){ vis[v] = 1; vector<pair<int,pair<int,int>>> tmp; for(auto u:adj[v]){ if(ok) return; if(vis[u.first] == 2){ continue; } if(vis[u.first] == 1){ if(ok) return; ok = 1; int now = u.first; while(now != 0){ ans.push_back(par[now]); now = par2[now]; } reverse(ans.begin(),ans.end()); vector<int> v1,v2; now = v; int cnt = 0; while(now != u.first){ assert(cnt++ <= 1000); v1.push_back(par[now]); v2.push_back(par[now] + 1); // cout << now << endl; now = par2[now]; } reverse(v1.begin(),v1.end()); reverse(v2.begin(),v2.end()); v1.push_back(u.second.first); v2.push_back(u.second.first + 1); for(int i = 0;i<v1.size();i++){ for(int j = 0;j<v1.size();j++){ ans.push_back(v1[i]); } for(int j = 0;j<v2.size();j++){ ans.push_back(v2[i]); } // for(auto u:v1){ // cout << u << ' '; // } // cout << endl; // for(auto u:v2){ // cout << u << ' '; // } // cout << endl; auto rt = [&](vector<int> a){ vector<int> ret = a; ret[0] = a.back(); for(int j = 0;j<a.size();j++) ret[j+1] = a[j]; return ret; }; v1 = rt(v1); v2 = rt(v2); // rotate(v1.begin(),v1.end(),next(v1.begin())); // rotate(v2.begin(),v2.end(),next(v2.begin())); } now = u.first; while(now != 0){ ans.push_back(par[now]); now = par2[now]; } return; } par[u.first] = u.second.first; par2[u.first] = v; dfs2(u.first,u.second.first); } vis[v] = 2; } variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V){ for(int i = 0;i<m;i+=2){ adj[U[i]].push_back({V[i],{i,i+1}}); // cout << U[i] << ' ' << V[i] << endl; } dfs2(0,-1); if(!ok) return false; return ans; }

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

islands.cpp: In function 'void dfs2(int, int)':
islands.cpp:45:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int i = 0;i<v1.size();i++){
      |                           ~^~~~~~~~~~
islands.cpp:46:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |                 for(int j = 0;j<v1.size();j++){
      |                               ~^~~~~~~~~~
islands.cpp:49:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 for(int j = 0;j<v2.size();j++){
      |                               ~^~~~~~~~~~
islands.cpp: In lambda function:
islands.cpp:63:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                     for(int j = 0;j<a.size();j++)
      |                                   ~^~~~~~~~~
#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...