oj.uz

Submission #802565

# Submission time Handle Problem Language Result Execution time Memory
802565 2023-08-02T12:46:29 Z SamAnd Fountain Parks (IOI21_parks) C++17
45 / 100
 1532 ms 127700 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];
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;
        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;
    vector<int> vv[2];
    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);
            vv[0].push_back(s[m_p(x + 1, y + 1)]);
            vv[1].push_back(s[m_p(x + 1, y - 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);
            vv[0].push_back(s[m_p(x + 1, y + 1)]);
            vv[1].push_back(s[m_p(x - 1, y + 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]);
        maxu = max(maxu, y[i]);
    }

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

    if (maxu <= 6)
    {
        for (int x = 0; x < (1 << sz(u)); ++x)
        {
            for (int i = 0; i < sz(u); ++i)
            {
                if (!(x & (1 << i)))
                {
                    a[i] = rs[vv[0][i]].fi;
                    b[i] = rs[vv[0][i]].se;
                }
                else
                {
                    a[i] = rs[vv[1][i]].fi;
                    b[i] = rs[vv[1][i]].se;
                }
            }
            vector<pair<int, int> > s;
            for (int i = 0; i < sz(u); ++i)
                s.push_back(m_p(a[i], b[i]));
            sort(all(s));
            bool f = true;
            for (int i = 0; i < sz(s) - 1; ++i)
            {
                if (s[i] == s[i + 1])
                {
                    f = false;
                    break;
                }
            }
            if (f)
                break;
        }
    }
    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

4
2 2
4 2
2 4
4 4
*/

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 16 ms 28816 KB Output is correct
3 Correct 15 ms 28404 KB Output is correct
4 Correct 16 ms 28848 KB Output is correct
5 Correct 15 ms 28840 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 14 ms 28356 KB Output is correct
8 Correct 17 ms 28376 KB Output is correct
9 Correct 530 ms 77648 KB Output is correct
10 Correct 35 ms 33860 KB Output is correct
11 Correct 164 ms 55324 KB Output is correct
12 Correct 47 ms 36200 KB Output is correct
13 Correct 115 ms 47568 KB Output is correct
14 Correct 17 ms 28884 KB Output is correct
15 Correct 19 ms 29204 KB Output is correct
16 Correct 501 ms 75784 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 16 ms 28816 KB Output is correct
3 Correct 15 ms 28404 KB Output is correct
4 Correct 16 ms 28848 KB Output is correct
5 Correct 15 ms 28840 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 14 ms 28356 KB Output is correct
8 Correct 17 ms 28376 KB Output is correct
9 Correct 530 ms 77648 KB Output is correct
10 Correct 35 ms 33860 KB Output is correct
11 Correct 164 ms 55324 KB Output is correct
12 Correct 47 ms 36200 KB Output is correct
13 Correct 115 ms 47568 KB Output is correct
14 Correct 17 ms 28884 KB Output is correct
15 Correct 19 ms 29204 KB Output is correct
16 Correct 501 ms 75784 KB Output is correct
17 Correct 17 ms 28756 KB Output is correct
18 Correct 17 ms 28868 KB Output is correct
19 Correct 15 ms 28864 KB Output is correct
20 Incorrect 15 ms 28864 KB Tree @(3, 5) appears more than once: for edges on positions 1 and 4
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 16 ms 28816 KB Output is correct
3 Correct 15 ms 28404 KB Output is correct
4 Correct 16 ms 28848 KB Output is correct
5 Correct 15 ms 28840 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 14 ms 28356 KB Output is correct
8 Correct 17 ms 28376 KB Output is correct
9 Correct 530 ms 77648 KB Output is correct
10 Correct 35 ms 33860 KB Output is correct
11 Correct 164 ms 55324 KB Output is correct
12 Correct 47 ms 36200 KB Output is correct
13 Correct 115 ms 47568 KB Output is correct
14 Correct 17 ms 28884 KB Output is correct
15 Correct 19 ms 29204 KB Output is correct
16 Correct 501 ms 75784 KB Output is correct
17 Correct 17 ms 28756 KB Output is correct
18 Correct 17 ms 28868 KB Output is correct
19 Correct 15 ms 28864 KB Output is correct
20 Incorrect 15 ms 28864 KB Tree @(3, 5) appears more than once: for edges on positions 1 and 4
21 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 16 ms 28816 KB Output is correct
3 Correct 15 ms 28404 KB Output is correct
4 Correct 16 ms 28848 KB Output is correct
5 Correct 15 ms 28840 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 14 ms 28356 KB Output is correct
8 Correct 17 ms 28376 KB Output is correct
9 Correct 530 ms 77648 KB Output is correct
10 Correct 35 ms 33860 KB Output is correct
11 Correct 164 ms 55324 KB Output is correct
12 Correct 47 ms 36200 KB Output is correct
13 Correct 115 ms 47568 KB Output is correct
14 Correct 17 ms 28884 KB Output is correct
15 Correct 19 ms 29204 KB Output is correct
16 Correct 501 ms 75784 KB Output is correct
17 Correct 15 ms 28776 KB Output is correct
18 Correct 15 ms 28824 KB Output is correct
19 Correct 15 ms 28420 KB Output is correct
20 Correct 981 ms 107848 KB Output is correct
21 Correct 1128 ms 99760 KB Output is correct
22 Correct 1006 ms 99912 KB Output is correct
23 Correct 942 ms 110152 KB Output is correct
24 Correct 224 ms 45652 KB Output is correct
25 Correct 1086 ms 108656 KB Output is correct
26 Correct 1101 ms 108592 KB Output is correct
27 Correct 1255 ms 117860 KB Output is correct
28 Correct 1183 ms 117844 KB Output is correct
29 Correct 1198 ms 117872 KB Output is correct
30 Correct 1195 ms 117792 KB Output is correct
31 Correct 15 ms 28756 KB Output is correct
32 Correct 57 ms 34164 KB Output is correct
33 Correct 90 ms 37068 KB Output is correct
34 Correct 1134 ms 107800 KB Output is correct
35 Correct 46 ms 31436 KB Output is correct
36 Correct 209 ms 43212 KB Output is correct
37 Correct 480 ms 57924 KB Output is correct
38 Correct 375 ms 56324 KB Output is correct
39 Correct 604 ms 66332 KB Output is correct
40 Correct 882 ms 77208 KB Output is correct
41 Correct 1069 ms 87116 KB Output is correct
42 Correct 1247 ms 97316 KB Output is correct
43 Correct 14 ms 28756 KB Output is correct
44 Correct 15 ms 28860 KB Output is correct
45 Correct 15 ms 28756 KB Output is correct
46 Correct 16 ms 28428 KB Output is correct
47 Correct 13 ms 28392 KB Output is correct
48 Correct 17 ms 28756 KB Output is correct
49 Correct 13 ms 28756 KB Output is correct
50 Correct 12 ms 28756 KB Output is correct
51 Correct 13 ms 28860 KB Output is correct
52 Correct 12 ms 28484 KB Output is correct
53 Correct 12 ms 28756 KB Output is correct
54 Correct 20 ms 29132 KB Output is correct
55 Correct 20 ms 29392 KB Output is correct
56 Correct 603 ms 68404 KB Output is correct
57 Correct 852 ms 86688 KB Output is correct
58 Correct 834 ms 86292 KB Output is correct
59 Correct 17 ms 28372 KB Output is correct
60 Correct 20 ms 28864 KB Output is correct
61 Correct 16 ms 28460 KB Output is correct
62 Correct 1155 ms 125088 KB Output is correct
63 Correct 1259 ms 125164 KB Output is correct
64 Correct 1224 ms 125816 KB Output is correct
65 Correct 25 ms 29776 KB Output is correct
66 Correct 37 ms 31040 KB Output is correct
67 Correct 553 ms 66288 KB Output is correct
68 Correct 925 ms 86388 KB Output is correct
69 Correct 1311 ms 103920 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 16 ms 28816 KB Output is correct
3 Correct 15 ms 28404 KB Output is correct
4 Correct 16 ms 28848 KB Output is correct
5 Correct 15 ms 28840 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 14 ms 28356 KB Output is correct
8 Correct 17 ms 28376 KB Output is correct
9 Correct 530 ms 77648 KB Output is correct
10 Correct 35 ms 33860 KB Output is correct
11 Correct 164 ms 55324 KB Output is correct
12 Correct 47 ms 36200 KB Output is correct
13 Correct 115 ms 47568 KB Output is correct
14 Correct 17 ms 28884 KB Output is correct
15 Correct 19 ms 29204 KB Output is correct
16 Correct 501 ms 75784 KB Output is correct
17 Correct 1169 ms 127700 KB Output is correct
18 Correct 1193 ms 124092 KB Output is correct
19 Correct 1119 ms 107556 KB Output is correct
20 Correct 1469 ms 106244 KB Output is correct
21 Correct 1139 ms 105852 KB Output is correct
22 Correct 17 ms 28856 KB Output is correct
23 Correct 136 ms 40352 KB Output is correct
24 Correct 79 ms 34764 KB Output is correct
25 Correct 345 ms 50464 KB Output is correct
26 Correct 764 ms 66672 KB Output is correct
27 Correct 591 ms 67408 KB Output is correct
28 Correct 791 ms 75472 KB Output is correct
29 Correct 1024 ms 87408 KB Output is correct
30 Correct 1206 ms 96632 KB Output is correct
31 Correct 1479 ms 105924 KB Output is correct
32 Correct 1532 ms 116156 KB Output is correct
33 Correct 1463 ms 127284 KB Output is correct
34 Correct 29 ms 30164 KB Output is correct
35 Correct 44 ms 31436 KB Output is correct
36 Correct 603 ms 68464 KB Output is correct
37 Correct 1002 ms 89168 KB Output is correct
38 Correct 1445 ms 109312 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28756 KB Output is correct
2 Correct 16 ms 28816 KB Output is correct
3 Correct 15 ms 28404 KB Output is correct
4 Correct 16 ms 28848 KB Output is correct
5 Correct 15 ms 28840 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 14 ms 28356 KB Output is correct
8 Correct 17 ms 28376 KB Output is correct
9 Correct 530 ms 77648 KB Output is correct
10 Correct 35 ms 33860 KB Output is correct
11 Correct 164 ms 55324 KB Output is correct
12 Correct 47 ms 36200 KB Output is correct
13 Correct 115 ms 47568 KB Output is correct
14 Correct 17 ms 28884 KB Output is correct
15 Correct 19 ms 29204 KB Output is correct
16 Correct 501 ms 75784 KB Output is correct
17 Correct 17 ms 28756 KB Output is correct
18 Correct 17 ms 28868 KB Output is correct
19 Correct 15 ms 28864 KB Output is correct
20 Incorrect 15 ms 28864 KB Tree @(3, 5) appears more than once: for edges on positions 1 and 4
21 Halted 0 ms 0 KB -