oj.uz

Submission #730265

# Submission time Handle Problem Language Result Execution time Memory
730265 2023-04-25T14:21:28 Z Nahian9696 Thousands Islands (IOI22_islands) C++17
31 / 100
 33 ms 6968 KB 
#include "islands.h"

#include <variant>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;


#define f0(i, n) for(int i = 0; i <  (n); i++)
#define f1(i, n) for(int i = 1; i <= (n); i++)
#define ff first
#define ss second
#define pb push_back

int opp(int n) {
    if(n % 2 == 0) return n+1;
    return n-1;
}


int viss[20005] = {0};

pair<bool, int> bfs(int u, int par, vi &cur, vector<pair<int, int>> grph[]) {
    cur.pb(u);

    for(auto nxt: grph[u]) {
        if(nxt.ff == par) continue;
        if(viss[nxt.ff]) {
            int n = cur.size();
            f0(i, n) if(cur[i] == nxt.ff) return {1, i};
        }
        viss[nxt.ff] = true;
        auto pp = bfs(nxt.ff, u, cur, grph);
        if(pp.ff) return pp;
    }

    cur.pop_back();
    return {0, -1};
}




std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {

    if(N == 2) {
        vi zr, on;
        f0(i, M) {
            if(U[i] == 0) zr.pb(i);
            else on.pb(i);
        }
        if(zr.size() < 2 || on.size() < 1) return false;
        return vi({zr[0], on[0], zr[1], zr[0], on[0], zr[1]});
    }

    bool sbtsk3 = (M % 2 == 0);
    bool sbtsk4 = (M % 2 == 0);

    f0(i, M - 1) {
        if(i % 2 == 0) {
            if(U[i] != V[i+1] || V[i] != U[i+1]) {
                sbtsk3 = false;
            }
            if(U[i] != U[i+1] || V[i] != V[i+1]) {
                sbtsk4 = false;
            }
        }
    }


    if(sbtsk3) {
        vector<pair<int, int>> grph[N];
        bool vis[N] = {0};
        f0(i, M) {
            grph[U[i]].pb({V[i], i});
        }
        vi ans, t_ans;

        int cur = 0;
        vis[cur] = true;

        if(grph[cur].size() > 1) {
            int x = grph[cur][0].ss, y = grph[cur][1].ss;
            return vi({x, opp(x), y, opp(y), opp(x), x, opp(y), y});
        } else if (grph[cur].size() == 0) {
            return false;
        } else {
            ans.pb(grph[cur][0].ss);
            cur = grph[cur][0].ff;
        }

        vis[cur] = true;

        while(grph[cur].size() <= 2) {
            if(grph[cur].size() == 1) return false;

            for(auto nxt: grph[cur]) {
                if(!vis[nxt.ff]) {
                    ans.pb(nxt.ss);
                    cur = nxt.ff;
                    vis[cur] = true;
                }
            }
        }

        for(auto nxt: grph[cur]) {
            if(!vis[nxt.ff]) {
                t_ans.pb(nxt.ss);
            }
        }
        int x = t_ans[0], y = t_ans[1];
        t_ans.clear();
        t_ans = vi(ans.rbegin(), ans.rend());

        ans.pb(x);
        ans.pb(opp(x));
        ans.pb(y);
        ans.pb(opp(y));
        ans.pb(opp(x));
        ans.pb(x);
        ans.pb(opp(y));
        ans.pb(y);

        for(int e: t_ans) ans.pb(e);

        return ans;
    }


    int mat[N][N];
    f0(i, M) {
        mat[U[i]][V[i]] = i;
    }
    vi ans;
    ans.pb(mat[0][1]);
    ans.pb(mat[1][0]);
    ans.pb(mat[0][2]);
    ans.pb(mat[2][0]);
    ans.pb(mat[1][0]);
    ans.pb(mat[0][1]);
    ans.pb(mat[2][0]);
    ans.pb(mat[0][2]);
    return ans;



    if(sbtsk4) {
        vector<pair<int, int>> grph[N];
        // bool vis[N] = {0};
        int mat[N][N];
        f0(i, M) {
            if(i % 2 == 0) {
                grph[U[i]].pb({V[i], i});
                mat[U[i]][V[i]] = i;
            }
        }

        vi cur;
        viss[0] = true;
        auto pp = bfs(0, -1, cur, grph);

        if(pp.ff) {
            vi ans, t_ans, t_t_ans;
            int k = pp.ss, n = cur.size();
            // cout << k << endl;

            f0(i, k) {
                ans.pb(mat[cur[i]][cur[i+1]]);
            }
            t_ans = vi(ans.rbegin(), ans.rend());
            for(int i = k; i < (n-1); i++) {
                t_t_ans.pb(mat[cur[i]][cur[i+1]]);
            }
            t_t_ans.pb(mat[cur[n-1]][cur[k]]);
            for(int p: t_t_ans) {
                ans.pb(p);
            }
            for(int p: t_t_ans) {
                ans.pb(opp(p));
                // cout << p << " ";
            }
            // cout << endl;
            t_t_ans = vi(t_t_ans.rbegin(), t_t_ans.rend());
            for(int p: t_t_ans) {
                ans.pb(p);
            }
            for(int p: t_t_ans) {
                ans.pb(opp(p));
            }
            for(int p: t_ans) {
                ans.pb(p);
            }
            return ans;
        }

        return false;
    }







    if (N == 4) {
        return std::vector<int>({0, 1, 2, 4, 0, 3, 2, 1, 4, 3});
    }
    return false;
}

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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 32 ms 4420 KB Output is correct

Subtask #2
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 32 ms 4632 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 19 ms 3020 KB Output is correct
18 Correct 15 ms 2616 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 30 ms 4640 KB Output is correct

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB Output is partially correct
2 Partially correct 1 ms 340 KB Output is partially correct
3 Partially correct 29 ms 3120 KB Output is partially correct
4 Partially correct 33 ms 6968 KB Output is partially correct
5 Partially correct 2 ms 3412 KB Output is partially correct
6 Partially correct 2 ms 3412 KB Output is partially correct
7 Correct 1 ms 212 KB Output is correct
8 Partially correct 0 ms 212 KB Output is partially correct
9 Partially correct 0 ms 212 KB Output is partially correct
10 Partially correct 2 ms 4180 KB Output is partially correct
11 Incorrect 2 ms 4180 KB Output isn't correct
12 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 32 ms 4420 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 32 ms 4632 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 19 ms 3020 KB Output is correct
31 Correct 15 ms 2616 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 30 ms 4640 KB Output is correct
37 Partially correct 0 ms 212 KB Output is partially correct
38 Correct 0 ms 212 KB Output is correct
39 Incorrect 0 ms 340 KB Output isn't correct
40 Halted 0 ms 0 KB -