oj.uz

Submission #802589

# Submission time Handle Problem Language Result Execution time Memory
802589 2023-08-02T12:50:27 Z SamAnd Fountain Parks (IOI21_parks) C++17
45 / 100
 1576 ms 127696 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;
        }
        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;
            }
        }
        assert(f);
    }
    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: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 14 ms 28792 KB Output is correct
2 Correct 13 ms 28812 KB Output is correct
3 Correct 13 ms 28372 KB Output is correct
4 Correct 12 ms 28860 KB Output is correct
5 Correct 13 ms 28756 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 13 ms 28404 KB Output is correct
8 Correct 13 ms 28372 KB Output is correct
9 Correct 501 ms 77596 KB Output is correct
10 Correct 37 ms 33856 KB Output is correct
11 Correct 158 ms 55284 KB Output is correct
12 Correct 51 ms 36288 KB Output is correct
13 Correct 123 ms 47604 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 21 ms 29196 KB Output is correct
16 Correct 504 ms 75668 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28792 KB Output is correct
2 Correct 13 ms 28812 KB Output is correct
3 Correct 13 ms 28372 KB Output is correct
4 Correct 12 ms 28860 KB Output is correct
5 Correct 13 ms 28756 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 13 ms 28404 KB Output is correct
8 Correct 13 ms 28372 KB Output is correct
9 Correct 501 ms 77596 KB Output is correct
10 Correct 37 ms 33856 KB Output is correct
11 Correct 158 ms 55284 KB Output is correct
12 Correct 51 ms 36288 KB Output is correct
13 Correct 123 ms 47604 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 21 ms 29196 KB Output is correct
16 Correct 504 ms 75668 KB Output is correct
17 Correct 12 ms 28756 KB Output is correct
18 Correct 12 ms 28784 KB Output is correct
19 Correct 14 ms 28860 KB Output is correct
20 Incorrect 13 ms 28756 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 14 ms 28792 KB Output is correct
2 Correct 13 ms 28812 KB Output is correct
3 Correct 13 ms 28372 KB Output is correct
4 Correct 12 ms 28860 KB Output is correct
5 Correct 13 ms 28756 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 13 ms 28404 KB Output is correct
8 Correct 13 ms 28372 KB Output is correct
9 Correct 501 ms 77596 KB Output is correct
10 Correct 37 ms 33856 KB Output is correct
11 Correct 158 ms 55284 KB Output is correct
12 Correct 51 ms 36288 KB Output is correct
13 Correct 123 ms 47604 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 21 ms 29196 KB Output is correct
16 Correct 504 ms 75668 KB Output is correct
17 Correct 12 ms 28756 KB Output is correct
18 Correct 12 ms 28784 KB Output is correct
19 Correct 14 ms 28860 KB Output is correct
20 Incorrect 13 ms 28756 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 14 ms 28792 KB Output is correct
2 Correct 13 ms 28812 KB Output is correct
3 Correct 13 ms 28372 KB Output is correct
4 Correct 12 ms 28860 KB Output is correct
5 Correct 13 ms 28756 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 13 ms 28404 KB Output is correct
8 Correct 13 ms 28372 KB Output is correct
9 Correct 501 ms 77596 KB Output is correct
10 Correct 37 ms 33856 KB Output is correct
11 Correct 158 ms 55284 KB Output is correct
12 Correct 51 ms 36288 KB Output is correct
13 Correct 123 ms 47604 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 21 ms 29196 KB Output is correct
16 Correct 504 ms 75668 KB Output is correct
17 Correct 16 ms 28756 KB Output is correct
18 Correct 13 ms 28872 KB Output is correct
19 Correct 13 ms 28372 KB Output is correct
20 Correct 1133 ms 107820 KB Output is correct
21 Correct 1280 ms 99832 KB Output is correct
22 Correct 1058 ms 99792 KB Output is correct
23 Correct 989 ms 110184 KB Output is correct
24 Correct 277 ms 45672 KB Output is correct
25 Correct 1228 ms 108648 KB Output is correct
26 Correct 1117 ms 108812 KB Output is correct
27 Correct 1206 ms 117760 KB Output is correct
28 Correct 1384 ms 117828 KB Output is correct
29 Correct 1334 ms 117860 KB Output is correct
30 Correct 1350 ms 117860 KB Output is correct
31 Correct 15 ms 28756 KB Output is correct
32 Correct 62 ms 34236 KB Output is correct
33 Correct 100 ms 37060 KB Output is correct
34 Correct 1116 ms 107828 KB Output is correct
35 Correct 40 ms 31408 KB Output is correct
36 Correct 177 ms 43104 KB Output is correct
37 Correct 441 ms 57940 KB Output is correct
38 Correct 385 ms 56360 KB Output is correct
39 Correct 566 ms 66264 KB Output is correct
40 Correct 769 ms 77160 KB Output is correct
41 Correct 1002 ms 87060 KB Output is correct
42 Correct 1211 ms 97252 KB Output is correct
43 Correct 16 ms 28756 KB Output is correct
44 Correct 15 ms 28824 KB Output is correct
45 Correct 15 ms 28756 KB Output is correct
46 Correct 15 ms 28368 KB Output is correct
47 Correct 15 ms 28372 KB Output is correct
48 Correct 15 ms 28756 KB Output is correct
49 Correct 14 ms 28756 KB Output is correct
50 Correct 13 ms 28756 KB Output is correct
51 Correct 14 ms 28820 KB Output is correct
52 Correct 13 ms 28428 KB Output is correct
53 Correct 15 ms 28772 KB Output is correct
54 Correct 20 ms 29140 KB Output is correct
55 Correct 20 ms 29384 KB Output is correct
56 Correct 551 ms 67988 KB Output is correct
57 Correct 816 ms 86176 KB Output is correct
58 Correct 853 ms 85864 KB Output is correct
59 Correct 17 ms 28456 KB Output is correct
60 Correct 15 ms 28816 KB Output is correct
61 Correct 16 ms 28580 KB Output is correct
62 Correct 1200 ms 124560 KB Output is correct
63 Correct 1177 ms 124716 KB Output is correct
64 Correct 1232 ms 125264 KB Output is correct
65 Correct 21 ms 29696 KB Output is correct
66 Correct 32 ms 30896 KB Output is correct
67 Correct 550 ms 65820 KB Output is correct
68 Correct 999 ms 85920 KB Output is correct
69 Correct 1383 ms 103348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28792 KB Output is correct
2 Correct 13 ms 28812 KB Output is correct
3 Correct 13 ms 28372 KB Output is correct
4 Correct 12 ms 28860 KB Output is correct
5 Correct 13 ms 28756 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 13 ms 28404 KB Output is correct
8 Correct 13 ms 28372 KB Output is correct
9 Correct 501 ms 77596 KB Output is correct
10 Correct 37 ms 33856 KB Output is correct
11 Correct 158 ms 55284 KB Output is correct
12 Correct 51 ms 36288 KB Output is correct
13 Correct 123 ms 47604 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 21 ms 29196 KB Output is correct
16 Correct 504 ms 75668 KB Output is correct
17 Correct 1227 ms 127696 KB Output is correct
18 Correct 1293 ms 124020 KB Output is correct
19 Correct 1323 ms 107572 KB Output is correct
20 Correct 1576 ms 106168 KB Output is correct
21 Correct 1337 ms 105804 KB Output is correct
22 Correct 14 ms 28756 KB Output is correct
23 Correct 171 ms 40340 KB Output is correct
24 Correct 87 ms 34868 KB Output is correct
25 Correct 386 ms 50456 KB Output is correct
26 Correct 663 ms 66692 KB Output is correct
27 Correct 653 ms 67612 KB Output is correct
28 Correct 807 ms 75548 KB Output is correct
29 Correct 1063 ms 87456 KB Output is correct
30 Correct 1213 ms 96744 KB Output is correct
31 Correct 1396 ms 106028 KB Output is correct
32 Correct 1449 ms 116228 KB Output is correct
33 Correct 1173 ms 127248 KB Output is correct
34 Correct 27 ms 30124 KB Output is correct
35 Correct 39 ms 31508 KB Output is correct
36 Correct 552 ms 68468 KB Output is correct
37 Correct 899 ms 89192 KB Output is correct
38 Correct 1323 ms 109352 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28792 KB Output is correct
2 Correct 13 ms 28812 KB Output is correct
3 Correct 13 ms 28372 KB Output is correct
4 Correct 12 ms 28860 KB Output is correct
5 Correct 13 ms 28756 KB Output is correct
6 Correct 15 ms 28372 KB Output is correct
7 Correct 13 ms 28404 KB Output is correct
8 Correct 13 ms 28372 KB Output is correct
9 Correct 501 ms 77596 KB Output is correct
10 Correct 37 ms 33856 KB Output is correct
11 Correct 158 ms 55284 KB Output is correct
12 Correct 51 ms 36288 KB Output is correct
13 Correct 123 ms 47604 KB Output is correct
14 Correct 16 ms 28884 KB Output is correct
15 Correct 21 ms 29196 KB Output is correct
16 Correct 504 ms 75668 KB Output is correct
17 Correct 12 ms 28756 KB Output is correct
18 Correct 12 ms 28784 KB Output is correct
19 Correct 14 ms 28860 KB Output is correct
20 Incorrect 13 ms 28756 KB Tree @(3, 5) appears more than once: for edges on positions 1 and 4
21 Halted 0 ms 0 KB -