Submission #728643

#	Time	Username	Problem	Language	Result	Execution time	Memory
728643		grogu	Thousands Islands (IOI22_islands)	C++17	55 / 100	169 ms	41464 KiB

islands

#include "islands.h"
#define here cerr<<"=======================\n"
#include <iostream>
#include <vector>
#include <variant>
#include <algorithm>
#include <set>
#define dbg(x) cerr<<#x<<": "<<x<<endl
#define ll int
#define pll pair<ll,ll>
#define pb push_back
#define popb pop_back
#define all(x_) x_.begin(), x_.end()
using namespace std;
#define maxn 1005
ll n,m;
vector<ll> g[maxn];
ll id[maxn][maxn];
vector<ll> allid[maxn][maxn];
set<pll> sss;
vector<ll> gen(vector<ll> v){
    vector<ll> ans;
    for(ll i = 0;i<=v.size()/2-1;i++) ans.pb(v[i]);
    for(ll i = v.size()-1;i>=v.size()/2;i--) ans.pb(v[i]);
    for(ll i = v.size()/2 - 1;i>=0;i--) ans.pb(v[i]);
    for(ll i = v.size()/2;i<=v.size()-1;i++) ans.pb(v[i]);
    return ans;
}
bool vis[maxn];
bool naso = 0;
ll x,y,tip;
vector<ll> cur;
void dfs1(ll u,ll p){
    vis[u] = 1;
    cur.pb(u);
    if(g[u].size()-(u!=p)>1){
        naso = 1;
        tip = 1;
        x = u;
        y = p;
        return;
    }
    for(ll s : g[u]){
        if(s==p) continue;
        if(vis[s]) continue;
        if(allid[u][s].size()>1){
            naso = 1;
            tip = 2;
            x = u;
            y = s;
            return;
        }
        dfs1(s,u);
        if(naso) return;
    }
    cur.popb();
}
bool sub = 1;
vector<ll> cyc;
ll in[maxn];
ll ti = 0;
void dfs2(ll u,ll p){
    vis[u] = 1;
    in[u] = 1;
    cur.pb(u);
    for(ll s : g[u]){
        if(vis[s]&&in[s]){
            while(cur.size()){
                cyc.pb(cur.back());
                if(cyc.back()==s) break;
                cur.popb();
            }
            naso = 1;
            return;
        }
        if(vis[s]) continue;
        dfs2(s,u);
        if(naso) return;
    }
    in[u] = 0;
    cur.popb();
}
void dfs3(ll u,ll p,ll en){
    cur.pb(u);
    if(u==en){
        naso = 1;
        return;
    }
    vis[u] = 1;
    for(ll s : g[u]){
        if(vis[s]) continue;
        dfs3(s,u,en);
        if(naso) return;
    }
    if(cur.size()) cur.popb();
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N;
    m = M;
    for(ll &x : U) x++;
    for(ll &x : V) x++;
    if(sub&&n==2){
        vector<vector<ll> > cnt(3);
        for(ll i = 0;i<m;i++){
            ll x = U[i],y = V[i];
            cnt[x].pb(i);
        }
        bool ok = cnt[1].size()>=2&&cnt[2].size()>=1;
        if(!ok) return ok;
        ll x = cnt[1][0],y = cnt[1][1];
        ll z = cnt[2][0];
        vector<ll> ans;
        ans.pb(x);
        ans.pb(z);
        ans.pb(y);
        ans.pb(x);
        ans.pb(z);
        ans.pb(y);
        return ans;
    }
    for(ll i = 1;i<=n;i++) for(ll j = 1;j<=n;j++) id[i][j] = -1;
    for(ll i = 0;i<m;i++){
        ll x = U[i],y = V[i];
        if(id[x][y]==-1) g[x].pb(y);
        id[x][y] = i;
        allid[x][y].pb(i);
        sss.insert({x,y});
    }
    if(sub&&n<=400&&sss.size()==n*(n-1)&&m==n*(n-1)){
        ll x = id[1][2];
        ll y = id[2][3];
        ll z = id[3][1];
        ll rx = id[2][1];
        ll ry = id[3][2];
        ll rz = id[1][3];
        vector<ll> ans = gen({x,y,z,rx,ry,rz});
        return ans;
    }
    bool sub2 = m%2==0;
    for(ll i = 0;i<m;i+=2) sub2&=(U[i]==V[i+1]&&V[i]==U[i+1]);
    if(n<=1000&&sub2){
        dfs1(1,1);
        if(!naso) return naso;
        if(tip==1){
            ll A = -1,B = -1;
            for(ll s : g[x]){
                if(s==y) continue;
                if(A==-1) A = s;
                else if(B==-1) B = s;
            }
            ll x1 = id[x][A];
            ll rx1 = id[A][x];
            ll y1 = id[x][B];
            ll ry1 = id[B][x];
            vector<ll> ans;
            for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
            ans.pb(x1);
            ans.pb(rx1);
            ans.pb(y1);
            ans.pb(ry1);
            ans.pb(rx1);
            ans.pb(x1);
            ans.pb(ry1);
            ans.pb(y1);
            for(ll i = cur.size()-2;i>=0;i--) ans.pb(id[cur[i]][cur[i+1]]);
            return ans;
        }else{
            ll x1 = allid[x][y][0];
            ll y1 = allid[x][y][1];
            ll rx1 = allid[y][x][0];
            ll ry1 = allid[y][x][1];
            vector<ll> ans;
            for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
            ans.pb(x1);
            ans.pb(rx1);
            ans.pb(y1);
            ans.pb(x1);
            ans.pb(rx1);
            ans.pb(y1);
            for(ll i = cur.size()-2;i>=0;i--) ans.pb(id[cur[i]][cur[i+1]]);
            return ans;
        }
    }
    dfs2(1,1);
    if(!naso) return naso;
    for(ll i = 1;i<=n;i++) vis[i] = 0;
    reverse(all(cyc));
    cur.clear();
    naso = 0;
    dfs3(1,1,cyc[0]);
    cyc.pb(cyc[0]);
    vector<ll> ans;
    for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
    for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][0]);
    for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][1]);
    for(ll i = cyc.size()-2;i>=0;i--) ans.pb(allid[cyc[i]][cyc[i+1]][0]);
    for(ll i = cyc.size()-2;i>=0;i--) ans.pb(allid[cyc[i]][cyc[i+1]][1]);
    for(ll i = cur.size()-2;i>=0;i--) ans.pb(id[cur[i]][cur[i+1]]);
    return ans;
}
/**
5 8
0 1
1 0
1 2
2 1
2 3
3 2
2 4
4 2

7 14
0 1
0 1
1 2
1 2
2 3
2 3
3 4
3 4
4 5
4 5
5 6
5 6
6 3
6 3
**/

Compilation message (stderr)

islands.cpp: In function 'std::vector<int> gen(std::vector<int>)':
islands.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(ll i = 0;i<=v.size()/2-1;i++) ans.pb(v[i]);
      |                  ~^~~~~~~~~~~~~~
islands.cpp:24:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(ll i = v.size()-1;i>=v.size()/2;i--) ans.pb(v[i]);
      |                           ~^~~~~~~~~~~~
islands.cpp:26:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(ll i = v.size()/2;i<=v.size()-1;i++) ans.pb(v[i]);
      |                           ~^~~~~~~~~~~~
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:105:25: warning: unused variable 'y' [-Wunused-variable]
  105 |             ll x = U[i],y = V[i];
      |                         ^
islands.cpp:129:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |     if(sub&&n<=400&&sss.size()==n*(n-1)&&m==n*(n-1)){
      |                     ~~~~~~~~~~^~~~~~~~~
islands.cpp:156:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |             for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
      |                          ~^~~~~~~~~~~~~
islands.cpp:173:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |             for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
      |                          ~^~~~~~~~~~~~~
islands.cpp:171:16: warning: unused variable 'ry1' [-Wunused-variable]
  171 |             ll ry1 = allid[y][x][1];
      |                ^~~
islands.cpp:193:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |     for(ll i = 0;i<cur.size()-1;i++) ans.pb(id[cur[i]][cur[i+1]]);
      |                  ~^~~~~~~~~~~~~
islands.cpp:194:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |     for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][0]);
      |                  ~^~~~~~~~~~~~~
islands.cpp:195:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |     for(ll i = 0;i<cyc.size()-1;i++) ans.pb(allid[cyc[i]][cyc[i+1]][1]);
      |                  ~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 0 / 45