oj.uz

Submission #819896

# Submission time Handle Problem Language Result Execution time Memory
819896 2023-08-10T15:10:49 Z HorizonWest Fountain Parks (IOI21_parks) C++17
5 / 100
 62 ms 36756 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 15 ms 11148 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Correct 12 ms 11152 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 13 ms 11200 KB Output is correct
7 Correct 13 ms 11164 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 54 ms 18380 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 33 ms 15220 KB Output is correct
12 Correct 18 ms 12244 KB Output is correct
13 Correct 19 ms 13216 KB Output is correct
14 Correct 12 ms 11268 KB Output is correct
15 Correct 12 ms 11284 KB Output is correct
16 Correct 54 ms 18336 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11148 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Correct 12 ms 11152 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 13 ms 11200 KB Output is correct
7 Correct 13 ms 11164 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 54 ms 18380 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 33 ms 15220 KB Output is correct
12 Correct 18 ms 12244 KB Output is correct
13 Correct 19 ms 13216 KB Output is correct
14 Correct 12 ms 11268 KB Output is correct
15 Correct 12 ms 11284 KB Output is correct
16 Correct 54 ms 18336 KB Output is correct
17 Incorrect 12 ms 11220 KB Tree (a[0], b[0]) = (5, 3) 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 15 ms 11148 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Correct 12 ms 11152 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 13 ms 11200 KB Output is correct
7 Correct 13 ms 11164 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 54 ms 18380 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 33 ms 15220 KB Output is correct
12 Correct 18 ms 12244 KB Output is correct
13 Correct 19 ms 13216 KB Output is correct
14 Correct 12 ms 11268 KB Output is correct
15 Correct 12 ms 11284 KB Output is correct
16 Correct 54 ms 18336 KB Output is correct
17 Incorrect 12 ms 11220 KB Tree (a[0], b[0]) = (5, 3) 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 15 ms 11148 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Correct 12 ms 11152 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 13 ms 11200 KB Output is correct
7 Correct 13 ms 11164 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 54 ms 18380 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 33 ms 15220 KB Output is correct
12 Correct 18 ms 12244 KB Output is correct
13 Correct 19 ms 13216 KB Output is correct
14 Correct 12 ms 11268 KB Output is correct
15 Correct 12 ms 11284 KB Output is correct
16 Correct 54 ms 18336 KB Output is correct
17 Runtime error 19 ms 22612 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 15 ms 11148 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Correct 12 ms 11152 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 13 ms 11200 KB Output is correct
7 Correct 13 ms 11164 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 54 ms 18380 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 33 ms 15220 KB Output is correct
12 Correct 18 ms 12244 KB Output is correct
13 Correct 19 ms 13216 KB Output is correct
14 Correct 12 ms 11268 KB Output is correct
15 Correct 12 ms 11284 KB Output is correct
16 Correct 54 ms 18336 KB Output is correct
17 Runtime error 62 ms 36756 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 15 ms 11148 KB Output is correct
2 Correct 12 ms 11220 KB Output is correct
3 Correct 12 ms 11136 KB Output is correct
4 Correct 12 ms 11152 KB Output is correct
5 Correct 12 ms 11220 KB Output is correct
6 Correct 13 ms 11200 KB Output is correct
7 Correct 13 ms 11164 KB Output is correct
8 Correct 12 ms 11228 KB Output is correct
9 Correct 54 ms 18380 KB Output is correct
10 Correct 16 ms 11988 KB Output is correct
11 Correct 33 ms 15220 KB Output is correct
12 Correct 18 ms 12244 KB Output is correct
13 Correct 19 ms 13216 KB Output is correct
14 Correct 12 ms 11268 KB Output is correct
15 Correct 12 ms 11284 KB Output is correct
16 Correct 54 ms 18336 KB Output is correct
17 Incorrect 12 ms 11220 KB Tree (a[0], b[0]) = (5, 3) is not adjacent to edge between u[0]=3 @(2, 2) and v[0]=2 @(4, 2)
18 Halted 0 ms 0 KB -