oj.uz

Submission #819897

# Submission time Handle Problem Language Result Execution time Memory
819897 2023-08-10T15:12:04 Z HorizonWest Fountain Parks (IOI21_parks) C++17
5 / 100
 61 ms 36740 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int Max = 2e5 + 7, Inf = 1e9 + 7;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

struct DSU
{
    vector <int> link, size;

    int find(int x)
    {
        while(x != link[x]) x = link[x];
        return x;
    }

    bool unite(int a, int b)
    {
        a = find(a); b = find(b);
        if(a == b) return false;
        if(size[a] < size[b]) swap(a, b);
        link[b] = a; size[a] += size[b];
        return true;
    }

    DSU(int n)
    {
        link.assign(n + 1, 1);
        size.assign(n + 1, 1);
        for(int i = 0; i <= n; i++)
            link[i] = i;
    }
};

int construct_roads(vector<int> x, vector<int> y)
{
    vector <vector<int>> g(Max + 1, vector <int> (4, 0));

    int n = (int) x.size();

    for(int i = 0; i < n; i++)
        g[y[i]][x[i]/2] = i + 1;

    vector <int> u, v, a, b; map <int, map <int, bool>> mp;

    DSU St(n);

    for(int i = 0; i < Max; i++)
    {
        if(g[i][1] != 0 && g[i][2] != 0)
        {
            u.pb(g[i][1]); v.pb(g[i][2]);
            a.pb(i-1); b.pb(5); mp[i-1][5] = 1;
            St.unite(g[i][1], g[i][2]);
        }

        if(g[i][2] != 0 && g[i][3] != 0)
        {
            u.pb(g[i][2]); v.pb(g[i][3]);
            a.pb(i+1); b.pb(3); mp[i+1][3] = 1;
            St.unite(g[i][2], g[i][3]);
        }
    }

    for(int i = 0; i < Max; i++)
    {
        if(g[i][1] != 0 && g[i-2][1] != 0)
        {
            if(St.unite(g[i][1], g[i-2][1]))
            {
                u.pb(g[i][1]); v.pb(g[i-2][1]);
                a.pb(i-1); b.pb(1);
            }
        }

        if(g[i][3] != 0 && g[i-2][3] != 0)
        {
            if(St.unite(g[i][3], g[i-2][3]))
            {
                u.pb(g[i][3]); v.pb(g[i-2][3]);
                a.pb(i-1); b.pb(7);
            }
        }

        if(g[i][2] != 0 && g[i-2][2] != 0)
        {
            if(St.unite(g[i][2], g[i-2][2]))
            {
                u.pb(g[i][2]); v.pb(g[i-2][2]);
                a.pb(i-1);
                if(!mp[i-1][5]) b.pb(5);
                else b.pb(3);
            }
        }
    }

    if(St.size[St.find(1)] != n)return 0;
    else
    {
        for(int i = 0; i < (int) u.size(); i++)
            u[i]--, v[i]--;
        build(u, v, b, a);
        return 1;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11220 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11196 KB Output is correct
4 Correct 12 ms 11228 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 12 ms 11220 KB Output is correct
7 Correct 13 ms 11220 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 56 ms 18364 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 38 ms 15180 KB Output is correct
12 Correct 19 ms 12244 KB Output is correct
13 Correct 18 ms 13220 KB Output is correct
14 Correct 12 ms 11220 KB Output is correct
15 Correct 13 ms 11316 KB Output is correct
16 Correct 56 ms 18412 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11220 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11196 KB Output is correct
4 Correct 12 ms 11228 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 12 ms 11220 KB Output is correct
7 Correct 13 ms 11220 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 56 ms 18364 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 38 ms 15180 KB Output is correct
12 Correct 19 ms 12244 KB Output is correct
13 Correct 18 ms 13220 KB Output is correct
14 Correct 12 ms 11220 KB Output is correct
15 Correct 13 ms 11316 KB Output is correct
16 Correct 56 ms 18412 KB Output is correct
17 Incorrect 13 ms 11212 KB Tree (a[0], b[0]) = (5, 1) is not adjacent to edge between u[0]=3 @(2, 2) and v[0]=2 @(4, 2)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11220 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11196 KB Output is correct
4 Correct 12 ms 11228 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 12 ms 11220 KB Output is correct
7 Correct 13 ms 11220 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 56 ms 18364 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 38 ms 15180 KB Output is correct
12 Correct 19 ms 12244 KB Output is correct
13 Correct 18 ms 13220 KB Output is correct
14 Correct 12 ms 11220 KB Output is correct
15 Correct 13 ms 11316 KB Output is correct
16 Correct 56 ms 18412 KB Output is correct
17 Incorrect 13 ms 11212 KB Tree (a[0], b[0]) = (5, 1) is not adjacent to edge between u[0]=3 @(2, 2) and v[0]=2 @(4, 2)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11220 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11196 KB Output is correct
4 Correct 12 ms 11228 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 12 ms 11220 KB Output is correct
7 Correct 13 ms 11220 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 56 ms 18364 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 38 ms 15180 KB Output is correct
12 Correct 19 ms 12244 KB Output is correct
13 Correct 18 ms 13220 KB Output is correct
14 Correct 12 ms 11220 KB Output is correct
15 Correct 13 ms 11316 KB Output is correct
16 Correct 56 ms 18412 KB Output is correct
17 Runtime error 21 ms 22648 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11220 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11196 KB Output is correct
4 Correct 12 ms 11228 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 12 ms 11220 KB Output is correct
7 Correct 13 ms 11220 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 56 ms 18364 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 38 ms 15180 KB Output is correct
12 Correct 19 ms 12244 KB Output is correct
13 Correct 18 ms 13220 KB Output is correct
14 Correct 12 ms 11220 KB Output is correct
15 Correct 13 ms 11316 KB Output is correct
16 Correct 56 ms 18412 KB Output is correct
17 Runtime error 61 ms 36740 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11220 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11196 KB Output is correct
4 Correct 12 ms 11228 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 12 ms 11220 KB Output is correct
7 Correct 13 ms 11220 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 56 ms 18364 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 38 ms 15180 KB Output is correct
12 Correct 19 ms 12244 KB Output is correct
13 Correct 18 ms 13220 KB Output is correct
14 Correct 12 ms 11220 KB Output is correct
15 Correct 13 ms 11316 KB Output is correct
16 Correct 56 ms 18412 KB Output is correct
17 Incorrect 13 ms 11212 KB Tree (a[0], b[0]) = (5, 1) is not adjacent to edge between u[0]=3 @(2, 2) and v[0]=2 @(4, 2)
18 Halted 0 ms 0 KB -