oj.uz

Submission #730415

# Submission time Handle Problem Language Result Execution time Memory
730415 2023-04-25T20:26:35 Z caganyanmaz Thousands Islands (IOI22_islands) C++17
26 / 100
 41 ms 6144 KB 
#include <bits/stdc++.h>
#define pb push_back
#define pp pop_back
using namespace std;


vector<int> path;
vector<bool> visited;
vector<vector<int>> g;
vector<array<int, 2>> edges;
vector<int> result;

void add(int next_node, int node)
{
        int next_edge;
        for (next_edge = 0; next_edge < g[next_node].size() && edges[g[next_node][next_edge]][1] != node; next_edge++);
        assert(next_edge < g[next_node].size());
        result.pb(g[next_node][next_edge]);
        reverse(g[next_node].begin(), g[next_node].end());
}

bool dfs(int node)
{
        if (g[node].size() > 2 || (g[node].size() > 1 && node == 0))
        {
                for (int i : path)
                        result.pb(i);
                if (node != 0)
                        for (int i = g[node].size()-1; i >= 0; i--)
                                if (edges[g[node][i]][1] == edges[path.back()][0])
                                        g[node].erase(next(g[node].begin(), i));
                for (int i = 0; i < 2; i++)
                {
                        result.pb(g[node][i]);
                        add(edges[g[node][i]][1], node);
                }
                int a = result[result.size()-3], b = result[result.size()-4], c=result[result.size()-1], d=result[result.size()-2];
                result.pb(a), result.pb(b), result.pb(c), result.pb(d);
                for (int i = path.size()-1; i >= 0; i--)
                        result.pb(path[i]);
                return true;
        }
        visited[node] = true;
        for (int edge : g[node])
        {
                if (visited[edges[edge][1]])
                        continue;
                path.pb(edge);
                if(dfs(edges[edge][1]))
                        return true;
        }
        path.pp();
        return false;
}



variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v)
{
        result.clear();
        path.clear();
        visited = vector<bool>(n, false);
        edges = vector<array<int, 2>>(m);
        for (int i = 0; i < m; i++)
                edges[i][0] = u[i], edges[i][1] = v[i];
        g = vector<vector<int>>(n);
        for (int i = 0; i < m; i++)
                g[edges[i][0]].pb(i);
        if(dfs(0))
                return result;
        return false;
}

Compilation message

islands.cpp: In function 'void add(int, int)':
islands.cpp:16:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (next_edge = 0; next_edge < g[next_node].size() && edges[g[next_node][next_edge]][1] != node; next_edge++);
      |                             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from islands.cpp:1:
islands.cpp:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         assert(next_edge < g[next_node].size());
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Correct 0 ms 300 KB Output is correct
4 Runtime error 1 ms 340 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 41 ms 6144 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 19 ms 3880 KB Output is correct
18 Correct 16 ms 3380 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 35 ms 6124 KB Output is correct

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 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 1 ms 212 KB Output is correct
2 Partially correct 1 ms 212 KB Output is partially correct
3 Correct 0 ms 300 KB Output is correct
4 Runtime error 1 ms 340 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -