Submission #907399

#	Time	Username	Problem	Language	Result	Execution time	Memory
907399		abcvuitunggio	Thousands Islands (IOI22_islands)	C++17	100 / 100	104 ms	31380 KiB

islands

#include "islands.h"
#include <variant>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector <int> u,v,ke[200001],ke2[200001],adj[200001],boring,res,ve;
int ch[200001],pos[200001],deg[200001],x,C;
void strain(){
    while (deg[x]==1){
        for (int i:ke[x]){
            int y=u[i]^v[i]^x;
            if (!ch[y]){
                boring.push_back(i);
                for (int i:ke2[x]){
                    int y=u[i]^v[i]^x;
                    if (!ch[u[i]^v[i]^x]&&!--deg[u[i]^v[i]^x])
                        ve.push_back(u[i]^v[i]^x);
                }
                C=0;
                ch[x]=1;
                x=y;
                break;
            }
        }
    }
}
void strain2(){
    while (!ve.empty()){
        C=0;
        int x=ve.back();
        ve.pop_back();
        ch[x]=1;
        for (int i:ke2[x]){
            int y=u[i]^v[i]^x;
            if (ch[y])
                continue;
            if (!--deg[y])
                ve.push_back(y);
        }
    }
}
pair <vector <int>, vector <int>> dfs(int s, int x){
    vector <int> ve,cycle;
    memset(pos,-1,sizeof(pos));
    ve.push_back(x);
    pos[x]=0;
    x=u[x]^v[x]^s;
    while (pos[adj[x][0]]==-1){
        int i=adj[x][0];
        int y=u[i]^v[i]^x;
        x=y;
        pos[i]=ve.size();
        ve.push_back(i);
    }
    x=adj[x][0];
    for (int i=pos[x];i<ve.size();i++)
        cycle.push_back(ve[i]);
    while (ve.size()>pos[x])
        ve.pop_back();
    return {ve,cycle};
}
bool check(vector <int> a, vector <int> b){
    if (a.size()!=b.size())
        return false;
    memset(ch,0,sizeof(ch));
    for (int i:a)
        ch[i]=1;
    int cnt=0;
    for (int i:b)
        cnt+=ch[i];
    return (cnt==a.size());
}
vector <int> rev(vector <int> v){
    reverse(v.begin(),v.end());
    return v;
}
vector <int> operator +(vector <int> a, vector <int> b){
    for (int i:b)
        a.push_back(i);
    return a;
}
variant <bool, vector <int>> find_journey(int n, int m, vector <int> U, vector <int> V) {
    u=U,v=V;
    for (int i=0;i<m;i++){
        ke[u[i]].push_back(i);
        ke2[v[i]].push_back(i);
        deg[u[i]]++;
    }
    for (int i=0;i<n;i++)
        if (!deg[i])
            ve.push_back(i);
    while (!C){
        C=1;
        strain();
        strain2();
    }
    if (ch[x])
        return false;
    for (int i=0;i<n;i++)
        for (int j:ke[i])
            if (!ch[u[j]^v[j]^i])
                adj[i].push_back(j);
    auto [ve,c]=dfs(x,adj[x][0]);
    auto [ve2,c2]=dfs(x,adj[x][1]);
    res=boring+ve+c+rev(ve)+ve2;
    if (!check(c,c2))
        res=res+c2+rev(ve2)+ve+rev(ve+c)+ve2;
    return res+rev(boring+ve2+c2);
}

Compilation message (stderr)

islands.cpp: In function 'void strain()':
islands.cpp:16:25: warning: unused variable 'y' [-Wunused-variable]
   16 |                     int y=u[i]^v[i]^x;
      |                         ^
islands.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > dfs(int, int)':
islands.cpp:57:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i=pos[x];i<ve.size();i++)
      |                       ~^~~~~~~~~~
islands.cpp:59:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     while (ve.size()>pos[x])
      |            ~~~~~~~~~^~~~~~~
islands.cpp: In function 'bool check(std::vector<int>, std::vector<int>)':
islands.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     return (cnt==a.size());
      |             ~~~^~~~~~~~~~

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