oj.uz

Submission #802707

# Submission time Handle Problem Language Result Execution time Memory
802707 2023-08-02T13:32:19 Z SamAnd Fountain Parks (IOI21_parks) C++17
5 / 100
 1483 ms 226284 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 400005;

int n;
vector<int> g[N];

bool c[N];
vector<int> uu, vv;
void dfs(int x)
{
    c[x] = true;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (c[h])
            continue;
        uu.push_back(x);
        vv.push_back(g[x][i]);
        dfs(h);
    }
}

vector<pair<int, int> > rs;
vector<int> gg[N], gi[N];
void dfs(int x, vector<int>& a, vector<int>& b)
{
    c[x] = true;
    for (int i = 0; i < gg[x].size(); ++i)
    {
        int h = gg[x][i];
        if (a[gi[x][i]] == -1)
        {
            a[gi[x][i]] = rs[x].fi;
            b[gi[x][i]] = rs[x].se;
        }
        if (!c[h])
            dfs(h, a, b);
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    std::vector<int> u, v, a, b;

    n = sz(x);
    vector<pair<int, int> > p;
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; ++i)
    {
        p.push_back(m_p(x[i], y[i]));
        mp[m_p(x[i], y[i])] = i;
    }

    int z = 0;
    map<pair<int, int>, int> s;
    for (int i = 0; i < n; ++i)
    {
        int x = p[i].fi;
        int y = p[i].se;
        if (mp.find(m_p(x + 2, y)) != mp.end())
        {
            u.push_back(mp[m_p(x, y)]);
            v.push_back(mp[m_p(x + 2, y)]);
            if (s.find(m_p(x + 1, y + 1)) == s.end())
                s[m_p(x + 1, y + 1)] = z++;
            if (s.find(m_p(x + 1, y - 1)) == s.end())
                s[m_p(x + 1, y - 1)] = z++;
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
            gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x + 1, y - 1)]);
            gg[s[m_p(x + 1, y - 1)]].push_back(s[m_p(x + 1, y + 1)]);
            gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
            gi[s[m_p(x + 1, y - 1)]].push_back(sz(u) - 1);
        }
        if (mp.find(m_p(x, y + 2)) != mp.end())
        {
            u.push_back(mp[m_p(x, y)]);
            v.push_back(mp[m_p(x, y + 2)]);
            if (s.find(m_p(x + 1, y + 1)) == s.end())
                s[m_p(x + 1, y + 1)] = z++;
            if (s.find(m_p(x - 1, y + 1)) == s.end())
                s[m_p(x - 1, y + 1)] = z++;
            g[u.back()].push_back(v.back());
            g[v.back()].push_back(u.back());
            gg[s[m_p(x + 1, y + 1)]].push_back(s[m_p(x - 1, y + 1)]);
            gg[s[m_p(x - 1, y + 1)]].push_back(s[m_p(x + 1, y + 1)]);
            gi[s[m_p(x + 1, y + 1)]].push_back(sz(u) - 1);
            gi[s[m_p(x - 1, y + 1)]].push_back(sz(u) - 1);
        }
    }

    rs.assign(z, m_p(0, 0));
    for (auto it = s.begin(); it != s.end(); ++it)
    {
        rs[it->se] = it->fi;
    }

    dfs(0);
    for (int i = 0; i < n; ++i)
    {
        if (!c[i])
            return 0;
    }

    int maxu = 0;
    for (int i = 0; i < n; ++i)
    {
        maxu = max(maxu, x[i]);
    }

    memset(c, false, sizeof c);
    a.assign(sz(u), -1);
    b.assign(sz(u), -1);

    if (maxu <= 6)
    {
        u = uu;
        v = vv;
        a.assign(sz(u), -1);
        b.assign(sz(u), -1);
        for (int i = 0; i < sz(u); ++i)
        {
            int mx = (x[u[i]] + x[v[i]]) / 2;
            int my = (y[u[i]] + y[v[i]]) / 2;
            if (mx % 2 == 0)
            {
                if (!c[s[m_p(mx - 1, my)]])
                {
                    a[i] = mx - 1;
                    b[i] = my;
                    c[s[m_p(mx - 1, my)]] = true;
                }
                else
                {
                    assert(!c[s[m_p(mx + 1, my)]]);
                    a[i] = mx + 1;
                    b[i] = my;
                    c[s[m_p(mx + 1, my)]] = true;
                }
            }
            else
            {
                assert(my % 2 == 0);
                if (!c[s[m_p(mx, my - 1)]])
                {
                    a[i] = mx;
                    b[i] = my - 1;
                    c[s[m_p(mx, my - 1)]] = true;
                }
                else
                {
                    assert(!c[s[m_p(mx, my + 1)]]);
                    a[i] = mx;
                    b[i] = my + 1;
                    c[s[m_p(mx, my + 1)]] = true;
                }
            }
        }
    }
    else
    {
        for (int i = 0; i < z; ++i)
        {
            if (!c[i] && sz(gg[i]) == 1)
            {
                dfs(i, a, b);
            }
        }
        for (int i = 0; i < z; ++i)
        {
            if (!c[i])
            {
                dfs(i, a, b);
            }
        }
    }

    build(u, v, a, b);
    return 1;
}

/*
3
2 2
4 2
2 4

3
4 2
2 2
4 4

3
4 4
4 2
2 4

4
4 2
4 4
2 2
2 4
*/

Compilation message

parks.cpp: In function 'void dfs(int)':
parks.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
parks.cpp: In function 'void dfs(int, std::vector<int>&, std::vector<int>&)':
parks.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < gg[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 13 ms 28756 KB Output is correct
3 Correct 13 ms 28396 KB Output is correct
4 Correct 14 ms 28776 KB Output is correct
5 Correct 14 ms 28864 KB Output is correct
6 Correct 14 ms 28480 KB Output is correct
7 Correct 15 ms 28500 KB Output is correct
8 Correct 14 ms 28480 KB Output is correct
9 Correct 490 ms 81676 KB Output is correct
10 Correct 35 ms 34132 KB Output is correct
11 Correct 174 ms 57488 KB Output is correct
12 Correct 48 ms 36868 KB Output is correct
13 Correct 115 ms 48836 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 18 ms 29268 KB Output is correct
16 Correct 500 ms 78456 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 13 ms 28756 KB Output is correct
3 Correct 13 ms 28396 KB Output is correct
4 Correct 14 ms 28776 KB Output is correct
5 Correct 14 ms 28864 KB Output is correct
6 Correct 14 ms 28480 KB Output is correct
7 Correct 15 ms 28500 KB Output is correct
8 Correct 14 ms 28480 KB Output is correct
9 Correct 490 ms 81676 KB Output is correct
10 Correct 35 ms 34132 KB Output is correct
11 Correct 174 ms 57488 KB Output is correct
12 Correct 48 ms 36868 KB Output is correct
13 Correct 115 ms 48836 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 18 ms 29268 KB Output is correct
16 Correct 500 ms 78456 KB Output is correct
17 Correct 14 ms 28756 KB Output is correct
18 Correct 15 ms 28872 KB Output is correct
19 Correct 14 ms 28756 KB Output is correct
20 Correct 13 ms 28868 KB Output is correct
21 Correct 15 ms 28480 KB Output is correct
22 Correct 17 ms 28864 KB Output is correct
23 Correct 1483 ms 117128 KB Output is correct
24 Runtime error 39 ms 58300 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 13 ms 28756 KB Output is correct
3 Correct 13 ms 28396 KB Output is correct
4 Correct 14 ms 28776 KB Output is correct
5 Correct 14 ms 28864 KB Output is correct
6 Correct 14 ms 28480 KB Output is correct
7 Correct 15 ms 28500 KB Output is correct
8 Correct 14 ms 28480 KB Output is correct
9 Correct 490 ms 81676 KB Output is correct
10 Correct 35 ms 34132 KB Output is correct
11 Correct 174 ms 57488 KB Output is correct
12 Correct 48 ms 36868 KB Output is correct
13 Correct 115 ms 48836 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 18 ms 29268 KB Output is correct
16 Correct 500 ms 78456 KB Output is correct
17 Correct 14 ms 28756 KB Output is correct
18 Correct 15 ms 28872 KB Output is correct
19 Correct 14 ms 28756 KB Output is correct
20 Correct 13 ms 28868 KB Output is correct
21 Correct 15 ms 28480 KB Output is correct
22 Correct 17 ms 28864 KB Output is correct
23 Correct 1483 ms 117128 KB Output is correct
24 Runtime error 39 ms 58300 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 13 ms 28756 KB Output is correct
3 Correct 13 ms 28396 KB Output is correct
4 Correct 14 ms 28776 KB Output is correct
5 Correct 14 ms 28864 KB Output is correct
6 Correct 14 ms 28480 KB Output is correct
7 Correct 15 ms 28500 KB Output is correct
8 Correct 14 ms 28480 KB Output is correct
9 Correct 490 ms 81676 KB Output is correct
10 Correct 35 ms 34132 KB Output is correct
11 Correct 174 ms 57488 KB Output is correct
12 Correct 48 ms 36868 KB Output is correct
13 Correct 115 ms 48836 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 18 ms 29268 KB Output is correct
16 Correct 500 ms 78456 KB Output is correct
17 Correct 15 ms 28864 KB Output is correct
18 Correct 13 ms 28868 KB Output is correct
19 Correct 14 ms 28372 KB Output is correct
20 Correct 941 ms 110624 KB Output is correct
21 Correct 1078 ms 106904 KB Output is correct
22 Correct 977 ms 105088 KB Output is correct
23 Correct 881 ms 114860 KB Output is correct
24 Correct 258 ms 47316 KB Output is correct
25 Correct 1101 ms 108536 KB Output is correct
26 Correct 1111 ms 108424 KB Output is correct
27 Correct 1181 ms 119668 KB Output is correct
28 Correct 1324 ms 119788 KB Output is correct
29 Correct 1226 ms 119852 KB Output is correct
30 Correct 1285 ms 119760 KB Output is correct
31 Correct 18 ms 28756 KB Output is correct
32 Correct 54 ms 34504 KB Output is correct
33 Correct 89 ms 38332 KB Output is correct
34 Correct 1116 ms 110728 KB Output is correct
35 Correct 39 ms 31532 KB Output is correct
36 Correct 186 ms 43456 KB Output is correct
37 Correct 423 ms 58368 KB Output is correct
38 Correct 402 ms 57512 KB Output is correct
39 Correct 546 ms 68000 KB Output is correct
40 Correct 793 ms 79024 KB Output is correct
41 Correct 1055 ms 88928 KB Output is correct
42 Correct 1211 ms 100152 KB Output is correct
43 Correct 14 ms 28756 KB Output is correct
44 Correct 16 ms 28756 KB Output is correct
45 Correct 17 ms 28756 KB Output is correct
46 Correct 14 ms 28436 KB Output is correct
47 Correct 15 ms 28484 KB Output is correct
48 Correct 15 ms 28756 KB Output is correct
49 Correct 15 ms 28824 KB Output is correct
50 Correct 15 ms 28756 KB Output is correct
51 Correct 15 ms 28864 KB Output is correct
52 Correct 15 ms 28372 KB Output is correct
53 Correct 15 ms 28756 KB Output is correct
54 Correct 18 ms 29140 KB Output is correct
55 Correct 20 ms 29380 KB Output is correct
56 Runtime error 422 ms 135744 KB Execution killed with signal 6
57 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 13 ms 28756 KB Output is correct
3 Correct 13 ms 28396 KB Output is correct
4 Correct 14 ms 28776 KB Output is correct
5 Correct 14 ms 28864 KB Output is correct
6 Correct 14 ms 28480 KB Output is correct
7 Correct 15 ms 28500 KB Output is correct
8 Correct 14 ms 28480 KB Output is correct
9 Correct 490 ms 81676 KB Output is correct
10 Correct 35 ms 34132 KB Output is correct
11 Correct 174 ms 57488 KB Output is correct
12 Correct 48 ms 36868 KB Output is correct
13 Correct 115 ms 48836 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 18 ms 29268 KB Output is correct
16 Correct 500 ms 78456 KB Output is correct
17 Correct 1078 ms 136328 KB Output is correct
18 Correct 1086 ms 130484 KB Output is correct
19 Correct 1084 ms 110236 KB Output is correct
20 Correct 1398 ms 109488 KB Output is correct
21 Correct 1103 ms 109248 KB Output is correct
22 Correct 15 ms 28756 KB Output is correct
23 Correct 125 ms 40880 KB Output is correct
24 Correct 72 ms 35128 KB Output is correct
25 Correct 304 ms 50724 KB Output is correct
26 Correct 624 ms 66796 KB Output is correct
27 Correct 609 ms 69912 KB Output is correct
28 Correct 827 ms 77940 KB Output is correct
29 Correct 1048 ms 91100 KB Output is correct
30 Correct 1297 ms 100576 KB Output is correct
31 Correct 1477 ms 110144 KB Output is correct
32 Runtime error 1184 ms 226284 KB Execution killed with signal 6
33 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28756 KB Output is correct
2 Correct 13 ms 28756 KB Output is correct
3 Correct 13 ms 28396 KB Output is correct
4 Correct 14 ms 28776 KB Output is correct
5 Correct 14 ms 28864 KB Output is correct
6 Correct 14 ms 28480 KB Output is correct
7 Correct 15 ms 28500 KB Output is correct
8 Correct 14 ms 28480 KB Output is correct
9 Correct 490 ms 81676 KB Output is correct
10 Correct 35 ms 34132 KB Output is correct
11 Correct 174 ms 57488 KB Output is correct
12 Correct 48 ms 36868 KB Output is correct
13 Correct 115 ms 48836 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 18 ms 29268 KB Output is correct
16 Correct 500 ms 78456 KB Output is correct
17 Correct 14 ms 28756 KB Output is correct
18 Correct 15 ms 28872 KB Output is correct
19 Correct 14 ms 28756 KB Output is correct
20 Correct 13 ms 28868 KB Output is correct
21 Correct 15 ms 28480 KB Output is correct
22 Correct 17 ms 28864 KB Output is correct
23 Correct 1483 ms 117128 KB Output is correct
24 Runtime error 39 ms 58300 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -