Submission #907229

#	Time	Username	Problem	Language	Result	Execution time	Memory
907229		abcvuitunggio	Thousands Islands (IOI22_islands)	C++17	19.25 / 100	55 ms	48620 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,fun,res,ve;
int n,m,ch[200001],pos[200001],deg[200001];
pair <vector <int>, vector <int>> dfs(int s, int x){
    vector <int> ve,cycle;
    memset(pos,-1,sizeof(pos));
    ve.push_back(x);
    x=u[x]^v[x]^s;
    while (pos[x]==-1){
        pos[x]=ve.size();
        int i=adj[x][0];
        int y=u[i]^v[i]^x;
        x=y;
        ve.push_back(i);
    }
    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){
    memset(ch,0,sizeof(ch));
    for (int i:a)
        ch[i]=1;
    for (int i:b)
        if (ch[i])
            return true;
    return false;
}
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) {
    n=N,m=M,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]){
            ch[i]=1;
            ve.push_back(i);
        }
    while (!ve.empty()){
        int x=ve.back();
        ve.pop_back();
        ch[x]=1;
        for (int i:ke2[x]){
            int y=u[i]^v[i]^x;
            if (!--deg[y])
                ve.push_back(y);
        }
    }
    if (ch[0])
        return false;
    int x=0;
    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])
                    deg[u[i]^v[i]^x]--;
                ch[x]=1;
                x=y;
                break;
            }
        }
    }
    if (!deg[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]);
    if (check(c,c2))
        fun=ve+c+rev(ve)+ve2+rev(c2)+rev(ve2);
    else
        fun=ve+c+rev(ve)+ve2+c2+rev(ve2)+ve+rev(c)+rev(ve)+ve2+rev(c2)+rev(ve2);
    return boring+fun+rev(boring);
}

Compilation message (stderr)

islands.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > dfs(int, int)':
islands.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i=pos[x];i<ve.size();i++)
      |                       ~^~~~~~~~~~
islands.cpp:23:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     while (ve.size()>pos[x])
      |            ~~~~~~~~~^~~~~~~

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