Submission #744712

#TimeUsernameProblemLanguageResultExecution timeMemory
744712kwongwengThousands Islands (IOI22_islands)C++17
26 / 100
32 ms10580 KiB
#include "islands.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef long double ld; typedef pair<ll, ll> pll; #define FOR(i, a, b) for(int i = a; i < b; i++) #define ROF(i, a, b) for(int i = a; i >= b; i--) #define ms memset #define pb push_back #define fi first #define se second int n; vi deg(1000); int mat[1000][1000][2]; /* vi ans; vi p(1000,-1); vi used(1000); void dfs(int u){ used[u]=1; FOR(v,0,n){ if (mat[u][v][0] == -1) continue; if (p[u]==v) continue; if (mat[u][v][1] != -1){ //cout << "PATH\n"; vi path; int w = u; while (w != 0){ path.pb(w); w=p[w]; } path.pb(0); ROF(i,path.size()-1,1){ ans.pb(mat[path[i]][path[i-1]][0]); } //e0[0], e1[0], e0[1], e0[0], e1[0], e0[1] vi path2 = {mat[u][v][0], mat[v][u][0], mat[u][v][1]}; FOR(i,0,2){ FOR(j,0,3) ans.pb(path2[j]); } FOR(i,1,path.size()){ ans.pb(mat[path[i]][path[i-1]][0]); } return; } if (used[v]){ // cycle 0-v-u //cout << "CYCLE\n"; vi path; int w = v; while (w != 0){ path.pb(w); w=p[w]; } path.pb(0); //path 0-v ROF(i,path.size()-1,1){ ans.pb(mat[path[i]][path[i-1]][0]); } vi cyc; w = u; while (w != v && w != 0){ cyc.pb(w); w=p[w]; } cyc.pb(v); //cycle 1 ans.pb(mat[v][u][0]); FOR(i,1,cyc.size()){ ans.pb(mat[cyc[i-1]][cyc[i]][0]); } //cycle 2 ROF(i,cyc.size()-1,1){ ans.pb(mat[cyc[i]][cyc[i-1]][0]); } ans.pb(mat[u][v][0]); //reverse cycle 1 ROF(i,cyc.size()-1,1){ ans.pb(mat[cyc[i-1]][cyc[i]][0]); } ans.pb(mat[v][u][0]); //reverse cycle 2 ans.pb(mat[u][v][0]); FOR(i,1,cyc.size()){ ans.pb(mat[cyc[i]][cyc[i-1]][0]); } //path v-0 FOR(i,1,path.size()){ ans.pb(mat[path[i]][path[i-1]][0]); } return; } if (deg[v] >= 3){ vi path; int w = v; while (w != 0){ path.pb(w); w=p[w]; } //path 0-v path.pb(0); ROF(i,path.size()-1,1){ ans.pb(mat[path[i]][path[i-1]][0]); } vi x; FOR(i,0,n){ if (mat[v][i][0]==-1) continue; if (u==i) continue; x.pb(i); if (x.size()==2) break; } vi sh = {mat[v][x[0]][0], mat[x[0]][v][0], mat[v][x[1]][0], mat[x[1]][v][0], mat[x[0]][v][0], mat[v][x[0]][0], mat[x[1]][v][0], mat[v][x[1]][0]}; FOR(i,0,8) ans.pb(sh[i]); //path v-0 FOR(i,1,path.size()){ ans.pb(mat[path[i]][path[i-1]][0]); } return; } p[v] = u; used[v] = 1; dfs(v); } } */ variant<bool, vi> find_journey(int N, int M, vi U, vi V) { n=N; if (N == 2){ vi e0, e1; FOR(i,0,M){ if (U[i]==0) e0.pb(i); else e1.pb(i); } if (e0.size() < 2 || e1.size() < 1) return false; return vi({e0[0], e1[0], e0[1], e0[0], e1[0], e0[1]}); } /* if (N <= 400 && M == N*(N-1)){ vii p = {{0,1},{1,2},{2,0},{0,2},{2,1},{1,0}}; vi l(6); FOR(i,0,M){ FOR(j,0,6){ if (p[j] == ii({U[i],V[i]})){ l[j] = i; } } } return vi({l[0],l[1],l[2],l[3],l[4],l[5],l[2],l[1],l[0],l[5],l[4],l[3]}); } */ if (N <= 1000 && U[0] != U[1]){ ms(mat, -1, sizeof(mat)); FOR(i,0,M){ // labelling edges int pos = 0; if (mat[U[i]][V[i]][0] != -1) pos = 1; mat[U[i]][V[i]][pos] = i; if (!pos) deg[U[i]]++; } /* dfs(0); if (ans.empty()) return false; return ans; */ vi p(N,-1); vi bfs; bfs.pb(0); vi used(N); used[0] = 1; FOR(k,0,bfs.size()){ int u = bfs[k]; FOR(i,0,N){ if (mat[u][i][0] == -1) continue; if (used[i] && p[u] != i){ // cycle found vi paru; int v = u; while (v != 0){ paru.pb(v); v = p[v]; } paru.pb(0); vi pari; v = i; while (v != 0){ pari.pb(v); v = p[v]; } pari.pb(0); reverse(paru.begin(),paru.end()); reverse(pari.begin(),pari.end()); int a = 0; vi ans; //path from 0 to cycle FOR(j,1,min(paru.size(),pari.size())){ if (paru[j] == pari[j]){ ans.pb(mat[paru[j-1]][paru[j]][0]); a=j; }else{ break; } } //first loop FOR(j,a+1,paru.size()){ ans.pb(mat[paru[j-1]][paru[j]][0]); } ans.pb(mat[u][i][0]); ROF(j,pari.size()-1,a+1){ ans.pb(mat[pari[j]][pari[j-1]][0]); } //second loop FOR(j,a+1,pari.size()){ ans.pb(mat[pari[j-1]][pari[j]][0]); } ans.pb(mat[i][u][0]); ROF(j,paru.size()-1,a+1){ ans.pb(mat[paru[j]][paru[j-1]][0]); } //reverse 1st loop FOR(j,a+1,pari.size()){ ans.pb(mat[pari[j]][pari[j-1]][0]); } ans.pb(mat[u][i][0]); ROF(j,paru.size()-1,a+1){ ans.pb(mat[paru[j-1]][paru[j]][0]); } //reverse 2nd loop FOR(j,a+1,paru.size()){ ans.pb(mat[paru[j]][paru[j-1]][0]); } ans.pb(mat[i][u][0]); ROF(j,pari.size()-1,a+1){ ans.pb(mat[pari[j-1]][pari[j]][0]); } //path back to 0 ROF(j,a,1){ ans.pb(mat[paru[j]][paru[j-1]][0]); } return ans; } if (mat[u][i][1] != -1 && p[u] != i){ // double edge found, solution from Subtask 1 vi par; int v = u; while (v != 0){ par.pb(v); v = p[v]; } par.pb(0); reverse(par.begin(), par.end()); vi ans; FOR(j,0,par.size()-1){ ans.pb(mat[par[j]][par[j+1]][0]); //path 0 -> u } // e0[0], e1[0], e0[1], e0[0], e1[0], e0[1] vi path = {mat[u][i][0], mat[i][u][0], mat[u][i][1], mat[u][i][0], mat[i][u][0], mat[u][i][1]}; FOR(j,0,6) ans.pb(path[j]); ROF(j,par.size()-2,0){ ans.pb(mat[par[j]][par[j+1]][0]); //path u -> 0 } return ans; } if (deg[i] >= 3){ vi path, ans; path.pb(i); int w = u; while (w != 0){ path.pb(w); w=p[w]; } //path 0-i path.pb(0); ROF(j,path.size()-1,1){ ans.pb(mat[path[j]][path[j-1]][0]); } vi x; FOR(j,0,n){ if (mat[i][j][0]==-1) continue; if (u==j) continue; x.pb(j); if (x.size()==2) break; } vi sh = {mat[i][x[0]][0], mat[x[0]][i][0], mat[i][x[1]][0], mat[x[1]][i][0], mat[x[0]][i][0], mat[i][x[0]][0], mat[x[1]][i][0], mat[i][x[1]][0]}; FOR(j,0,8) ans.pb(sh[j]); //path i-0 FOR(j,1,path.size()){ ans.pb(mat[path[j]][path[j-1]][0]); } return ans; } if (used[i]) continue; used[i] = 1; p[i] = u; bfs.pb(i); } } } return false; }

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, vi, vi)':
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  173 |     FOR(k,0,bfs.size()){
      |         ~~~~~~~~~~~~~~                 
islands.cpp:173:5: note: in expansion of macro 'FOR'
  173 |     FOR(k,0,bfs.size()){
      |     ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  195 |           FOR(j,1,min(paru.size(),pari.size())){
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:195:11: note: in expansion of macro 'FOR'
  195 |           FOR(j,1,min(paru.size(),pari.size())){
      |           ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  204 |           FOR(j,a+1,paru.size()){
      |               ~~~~~~~~~~~~~~~~~        
islands.cpp:204:11: note: in expansion of macro 'FOR'
  204 |           FOR(j,a+1,paru.size()){
      |           ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  212 |           FOR(j,a+1,pari.size()){
      |               ~~~~~~~~~~~~~~~~~        
islands.cpp:212:11: note: in expansion of macro 'FOR'
  212 |           FOR(j,a+1,pari.size()){
      |           ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  220 |           FOR(j,a+1,pari.size()){
      |               ~~~~~~~~~~~~~~~~~        
islands.cpp:220:11: note: in expansion of macro 'FOR'
  220 |           FOR(j,a+1,pari.size()){
      |           ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  228 |           FOR(j,a+1,paru.size()){
      |               ~~~~~~~~~~~~~~~~~        
islands.cpp:228:11: note: in expansion of macro 'FOR'
  228 |           FOR(j,a+1,paru.size()){
      |           ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  251 |           FOR(j,0,par.size()-1){
      |               ~~~~~~~~~~~~~~~~         
islands.cpp:251:11: note: in expansion of macro 'FOR'
  251 |           FOR(j,0,par.size()-1){
      |           ^~~
islands.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  285 |           FOR(j,1,path.size()){
      |               ~~~~~~~~~~~~~~~          
islands.cpp:285:11: note: in expansion of macro 'FOR'
  285 |           FOR(j,1,path.size()){
      |           ^~~
#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...