oj.uz

Submission #907260

# Submission time Handle Problem Language Result Execution time Memory
907260 2024-01-15T10:26:22 Z abcvuitunggio Thousands Islands (IOI22_islands) C++17
31 / 100
 49 ms 45212 KB 
#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);
    pos[x]=0;
    x=u[x]^v[x]^s;
    while (true){
        int i=adj[x][0];
        int y=u[i]^v[i]^x;
        x=y;
        if (pos[i]!=-1){
            x=i;
            break;
        }
        pos[i]=ve.size();
        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){
    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) {
    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++)
        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[x])
        return false;
    for (int i=0;i<n;i++){
        if (ch[i])
            continue;
        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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15704 KB Output is correct
2 Correct 6 ms 15960 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 5 ms 15704 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 44 ms 23180 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15964 KB Output is correct
2 Correct 4 ms 15708 KB Output is correct
3 Correct 4 ms 16084 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 40 ms 22356 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16220 KB Output is correct
2 Correct 5 ms 15704 KB Output is correct
3 Correct 7 ms 15704 KB Output is correct
4 Correct 5 ms 15964 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 5 ms 15704 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 5 ms 15964 KB Output is correct
10 Correct 5 ms 16220 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 6 ms 16220 KB Output is correct
13 Correct 5 ms 15708 KB Output is correct
14 Correct 5 ms 15708 KB Output is correct
15 Correct 5 ms 15964 KB Output is correct
16 Correct 5 ms 15708 KB Output is correct
17 Correct 23 ms 20052 KB Output is correct
18 Correct 22 ms 19576 KB Output is correct
19 Correct 6 ms 15708 KB Output is correct
20 Correct 6 ms 15964 KB Output is correct
21 Correct 6 ms 16048 KB Output is correct
22 Correct 6 ms 15964 KB Output is correct
23 Correct 29 ms 22364 KB Output is correct

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 15708 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 5 ms 15704 KB Output is correct
2 Correct 6 ms 15960 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 5 ms 15704 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 5 ms 15964 KB Output is correct
7 Correct 44 ms 23180 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 4 ms 15708 KB Output is correct
10 Correct 4 ms 16084 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 4 ms 15964 KB Output is correct
13 Correct 40 ms 22356 KB Output is correct
14 Correct 6 ms 16220 KB Output is correct
15 Correct 5 ms 15704 KB Output is correct
16 Correct 7 ms 15704 KB Output is correct
17 Correct 5 ms 15964 KB Output is correct
18 Correct 5 ms 15960 KB Output is correct
19 Correct 5 ms 15964 KB Output is correct
20 Correct 5 ms 15704 KB Output is correct
21 Correct 5 ms 15964 KB Output is correct
22 Correct 5 ms 15964 KB Output is correct
23 Correct 5 ms 16220 KB Output is correct
24 Correct 5 ms 15964 KB Output is correct
25 Correct 6 ms 16220 KB Output is correct
26 Correct 5 ms 15708 KB Output is correct
27 Correct 5 ms 15708 KB Output is correct
28 Correct 5 ms 15964 KB Output is correct
29 Correct 5 ms 15708 KB Output is correct
30 Correct 23 ms 20052 KB Output is correct
31 Correct 22 ms 19576 KB Output is correct
32 Correct 6 ms 15708 KB Output is correct
33 Correct 6 ms 15964 KB Output is correct
34 Correct 6 ms 16048 KB Output is correct
35 Correct 6 ms 15964 KB Output is correct
36 Correct 29 ms 22364 KB Output is correct
37 Correct 6 ms 15964 KB Output is correct
38 Correct 6 ms 15708 KB Output is correct
39 Correct 5 ms 15708 KB Output is correct
40 Correct 6 ms 15964 KB Output is correct
41 Correct 17 ms 18880 KB Output is correct
42 Correct 7 ms 15964 KB Output is correct
43 Correct 33 ms 21672 KB Output is correct
44 Runtime error 49 ms 45212 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -