oj.uz

Submission #798134

# Submission time Handle Problem Language Result Execution time Memory
798134 2023-07-30T11:42:03 Z MilosMilutinovic Thousands Islands (IOI22_islands) C++17
31 / 100
 34 ms 10324 KB 
#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector < pair <int, int> > g[N];
vector < pair <int, int> > G[N];
int conn[500][500], pp[N], par[N];
pair <int, int> go_up[N];
bool was[N], good;
vector <int> cyc;
void dfs_cyc(int x, int fa) {
  if (!cyc.empty()) return;
    was[x] = true;
  int cnt = 0;
    vector<int> ch;
    for (auto& p : G[x]) {
        int y = p.first;
        int id = p.second;
        if (id / 2 == fa / 2) continue;
        ch.push_back(id);
        if (was[y]) {
            int ver = x;
            while (false && ver != y) {
                cyc.push_back(go_up[ver].second);
                ver = go_up[ver].first;
            }
            //reverse(cyc.begin(), cyc.end());
         
          cnt++;
            continue;
        }
      cnt++;
        go_up[y] = {x, id};
        pp[y] = id;
        par[y] = x;
        dfs_cyc(y, id);
        if (!cyc.empty()) return;
    }
  if (cnt >= 2) {
    good = true;
    int v = x;
    vector<int> gg;
    while (v > 0) {
      gg.push_back(pp[v]);
      v = par[v];
    }
    reverse(gg.begin(), gg.end());
    for (int i : gg) cyc.push_back(i);
    cyc.push_back(ch[0]);
    cyc.push_back(ch[0] ^ 1);
    cyc.push_back(ch[1]);
    cyc.push_back(ch[1] ^ 1);
    cyc.push_back(ch[0] ^ 1);
    cyc.push_back(ch[0]);
    cyc.push_back(ch[1] ^ 1);
    cyc.push_back(ch[1]);
    reverse(gg.begin(), gg.end());
    for (int i : gg) cyc.push_back(i);
    return;
  }
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
 
    for (int i = 0; i < M; i++) {
        g[U[i]].emplace_back(V[i], i);
    }
 
    if (N == 2) {
        if (g[0].size() >= 2 && g[1].size() >= 1) {
            vector <int> ans;
            ans.push_back(g[0][0].second);
            ans.push_back(g[1][0].second);
            ans.push_back(g[0][1].second);
            ans.push_back(g[0][0].second);
            ans.push_back(g[1][0].second);
            ans.push_back(g[0][1].second);
            return ans;
        } else return false;
    }
 
    if (N <= 400) {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                conn[i][j] = -1;
        for (int i = 0; i < M; i++)
            conn[U[i]][V[i]] = i;
        bool sub2 = true;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (i != j && conn[i][j] == -1)
                    sub2 = false;
        if (sub2) {
            vector <int> ans;
 
            ans.push_back(conn[0][1]);
            ans.push_back(conn[1][2]);
            ans.push_back(conn[2][0]);
 
            ans.push_back(conn[0][2]);
            ans.push_back(conn[2][1]);
            ans.push_back(conn[1][0]);
 
            ans.push_back(conn[2][0]);
            ans.push_back(conn[1][2]);
            ans.push_back(conn[0][1]);
 
            ans.push_back(conn[1][0]);
            ans.push_back(conn[2][1]);
            ans.push_back(conn[0][2]);
 
            return ans;
        }
    }
 
    bool sub3 = (M % 2 == 0);
    for (int i = 0; i < M - 1; i += 2)
        sub3 = (sub3 & (U[i] == V[i + 1]) & (V[i] == U[i + 1]));
 
    if (sub3) {
        for (int i = 0; i < M; i += 2) {
            G[U[i]].emplace_back(V[i], i);
            G[V[i]].emplace_back(U[i], i + 1);
        }
        dfs_cyc(0, -3);
        if (!good) return false;
        return cyc;
    }
 
    assert(false);
 
    return false;
 
    if (N == 4) {
        return 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 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 28 ms 9884 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 34 ms 10092 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5192 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 5204 KB Output is correct
9 Correct 2 ms 5204 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 5332 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 3 ms 5136 KB Output is correct
15 Correct 2 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 25 ms 9000 KB Output is correct
18 Correct 15 ms 8592 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 25 ms 10088 KB Output is correct

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 10324 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 28 ms 9884 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 34 ms 10092 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5192 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4960 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 5204 KB Output is correct
22 Correct 2 ms 5204 KB Output is correct
23 Correct 3 ms 5332 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 3 ms 5332 KB Output is correct
26 Correct 3 ms 5204 KB Output is correct
27 Correct 3 ms 5136 KB Output is correct
28 Correct 2 ms 5204 KB Output is correct
29 Correct 3 ms 5204 KB Output is correct
30 Correct 25 ms 9000 KB Output is correct
31 Correct 15 ms 8592 KB Output is correct
32 Correct 2 ms 4948 KB Output is correct
33 Correct 3 ms 4948 KB Output is correct
34 Correct 2 ms 4948 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 25 ms 10088 KB Output is correct
37 Runtime error 6 ms 9940 KB Execution killed with signal 6
38 Halted 0 ms 0 KB -