oj.uz

Submission #744712

# Submission time Handle Problem Language Result Execution time Memory
744712 2023-05-19T03:00:01 Z kwongweng Thousands Islands (IOI22_islands) C++17
26 / 100
 32 ms 10580 KB 
#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

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()){
      |           ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 32 ms 4368 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 4 ms 8020 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 4 ms 8020 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 5 ms 8020 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 4 ms 8020 KB Output is correct
9 Correct 4 ms 8020 KB Output is correct
10 Correct 6 ms 8176 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 6 ms 8148 KB Output is correct
13 Correct 3 ms 8020 KB Output is correct
14 Correct 3 ms 8020 KB Output is correct
15 Correct 4 ms 8020 KB Output is correct
16 Correct 4 ms 8020 KB Output is correct
17 Correct 20 ms 9680 KB Output is correct
18 Correct 16 ms 9396 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 4 ms 8020 KB Output is correct
21 Correct 4 ms 8020 KB Output is correct
22 Correct 3 ms 8020 KB Output is correct
23 Correct 28 ms 10580 KB Output is correct

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 32 ms 4368 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -