oj.uz

Submission #802558

# Submission time Handle Problem Language Result Execution time Memory
802558 2023-08-02T12:45:24 Z SamAnd Fountain Parks (IOI21_parks) C++17
25 / 100
 1531 ms 128868 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[0][i]].fi;
                    b[i] = rs[vv[0][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 16 ms 28772 KB Output is correct
2 Correct 16 ms 28772 KB Output is correct
3 Correct 18 ms 28484 KB Output is correct
4 Correct 17 ms 28844 KB Output is correct
5 Correct 17 ms 28812 KB Output is correct
6 Correct 17 ms 28472 KB Output is correct
7 Correct 18 ms 28472 KB Output is correct
8 Correct 17 ms 28372 KB Output is correct
9 Correct 561 ms 78424 KB Output is correct
10 Correct 41 ms 33884 KB Output is correct
11 Correct 167 ms 55652 KB Output is correct
12 Correct 58 ms 36308 KB Output is correct
13 Correct 123 ms 47996 KB Output is correct
14 Correct 17 ms 28868 KB Output is correct
15 Correct 22 ms 29264 KB Output is correct
16 Correct 510 ms 76380 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28772 KB Output is correct
2 Correct 16 ms 28772 KB Output is correct
3 Correct 18 ms 28484 KB Output is correct
4 Correct 17 ms 28844 KB Output is correct
5 Correct 17 ms 28812 KB Output is correct
6 Correct 17 ms 28472 KB Output is correct
7 Correct 18 ms 28472 KB Output is correct
8 Correct 17 ms 28372 KB Output is correct
9 Correct 561 ms 78424 KB Output is correct
10 Correct 41 ms 33884 KB Output is correct
11 Correct 167 ms 55652 KB Output is correct
12 Correct 58 ms 36308 KB Output is correct
13 Correct 123 ms 47996 KB Output is correct
14 Correct 17 ms 28868 KB Output is correct
15 Correct 22 ms 29264 KB Output is correct
16 Correct 510 ms 76380 KB Output is correct
17 Incorrect 17 ms 28756 KB Tree @(3, 3) appears more than once: for edges on positions 2 and 3
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28772 KB Output is correct
2 Correct 16 ms 28772 KB Output is correct
3 Correct 18 ms 28484 KB Output is correct
4 Correct 17 ms 28844 KB Output is correct
5 Correct 17 ms 28812 KB Output is correct
6 Correct 17 ms 28472 KB Output is correct
7 Correct 18 ms 28472 KB Output is correct
8 Correct 17 ms 28372 KB Output is correct
9 Correct 561 ms 78424 KB Output is correct
10 Correct 41 ms 33884 KB Output is correct
11 Correct 167 ms 55652 KB Output is correct
12 Correct 58 ms 36308 KB Output is correct
13 Correct 123 ms 47996 KB Output is correct
14 Correct 17 ms 28868 KB Output is correct
15 Correct 22 ms 29264 KB Output is correct
16 Correct 510 ms 76380 KB Output is correct
17 Incorrect 17 ms 28756 KB Tree @(3, 3) appears more than once: for edges on positions 2 and 3
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28772 KB Output is correct
2 Correct 16 ms 28772 KB Output is correct
3 Correct 18 ms 28484 KB Output is correct
4 Correct 17 ms 28844 KB Output is correct
5 Correct 17 ms 28812 KB Output is correct
6 Correct 17 ms 28472 KB Output is correct
7 Correct 18 ms 28472 KB Output is correct
8 Correct 17 ms 28372 KB Output is correct
9 Correct 561 ms 78424 KB Output is correct
10 Correct 41 ms 33884 KB Output is correct
11 Correct 167 ms 55652 KB Output is correct
12 Correct 58 ms 36308 KB Output is correct
13 Correct 123 ms 47996 KB Output is correct
14 Correct 17 ms 28868 KB Output is correct
15 Correct 22 ms 29264 KB Output is correct
16 Correct 510 ms 76380 KB Output is correct
17 Correct 17 ms 28856 KB Output is correct
18 Correct 16 ms 28844 KB Output is correct
19 Correct 16 ms 28480 KB Output is correct
20 Correct 1173 ms 109412 KB Output is correct
21 Correct 1192 ms 101056 KB Output is correct
22 Correct 1130 ms 101096 KB Output is correct
23 Correct 941 ms 111184 KB Output is correct
24 Correct 227 ms 46652 KB Output is correct
25 Correct 1157 ms 109624 KB Output is correct
26 Correct 1153 ms 109648 KB Output is correct
27 Correct 1293 ms 118416 KB Output is correct
28 Correct 1244 ms 118196 KB Output is correct
29 Correct 1355 ms 118160 KB Output is correct
30 Correct 1288 ms 118180 KB Output is correct
31 Correct 13 ms 28756 KB Output is correct
32 Correct 60 ms 34352 KB Output is correct
33 Correct 122 ms 37592 KB Output is correct
34 Correct 1307 ms 108352 KB Output is correct
35 Correct 48 ms 31564 KB Output is correct
36 Correct 217 ms 43668 KB Output is correct
37 Correct 474 ms 58384 KB Output is correct
38 Correct 386 ms 56820 KB Output is correct
39 Correct 600 ms 66772 KB Output is correct
40 Correct 773 ms 77748 KB Output is correct
41 Correct 1006 ms 87636 KB Output is correct
42 Correct 1376 ms 97756 KB Output is correct
43 Correct 16 ms 28848 KB Output is correct
44 Correct 15 ms 28836 KB Output is correct
45 Correct 15 ms 28868 KB Output is correct
46 Correct 15 ms 28432 KB Output is correct
47 Correct 16 ms 28580 KB Output is correct
48 Incorrect 16 ms 28792 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
49 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28772 KB Output is correct
2 Correct 16 ms 28772 KB Output is correct
3 Correct 18 ms 28484 KB Output is correct
4 Correct 17 ms 28844 KB Output is correct
5 Correct 17 ms 28812 KB Output is correct
6 Correct 17 ms 28472 KB Output is correct
7 Correct 18 ms 28472 KB Output is correct
8 Correct 17 ms 28372 KB Output is correct
9 Correct 561 ms 78424 KB Output is correct
10 Correct 41 ms 33884 KB Output is correct
11 Correct 167 ms 55652 KB Output is correct
12 Correct 58 ms 36308 KB Output is correct
13 Correct 123 ms 47996 KB Output is correct
14 Correct 17 ms 28868 KB Output is correct
15 Correct 22 ms 29264 KB Output is correct
16 Correct 510 ms 76380 KB Output is correct
17 Correct 1154 ms 128868 KB Output is correct
18 Correct 1190 ms 124812 KB Output is correct
19 Correct 1120 ms 108088 KB Output is correct
20 Correct 1531 ms 106756 KB Output is correct
21 Correct 1177 ms 106272 KB Output is correct
22 Correct 15 ms 28868 KB Output is correct
23 Correct 134 ms 40696 KB Output is correct
24 Correct 79 ms 35108 KB Output is correct
25 Correct 362 ms 50944 KB Output is correct
26 Correct 739 ms 67276 KB Output is correct
27 Correct 694 ms 67916 KB Output is correct
28 Correct 887 ms 75972 KB Output is correct
29 Correct 1030 ms 87912 KB Output is correct
30 Correct 1309 ms 97204 KB Output is correct
31 Correct 1383 ms 106428 KB Output is correct
32 Correct 1447 ms 116688 KB Output is correct
33 Correct 1206 ms 127920 KB Output is correct
34 Correct 28 ms 30236 KB Output is correct
35 Correct 37 ms 31536 KB Output is correct
36 Correct 538 ms 68884 KB Output is correct
37 Correct 911 ms 89672 KB Output is correct
38 Correct 1327 ms 109852 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28772 KB Output is correct
2 Correct 16 ms 28772 KB Output is correct
3 Correct 18 ms 28484 KB Output is correct
4 Correct 17 ms 28844 KB Output is correct
5 Correct 17 ms 28812 KB Output is correct
6 Correct 17 ms 28472 KB Output is correct
7 Correct 18 ms 28472 KB Output is correct
8 Correct 17 ms 28372 KB Output is correct
9 Correct 561 ms 78424 KB Output is correct
10 Correct 41 ms 33884 KB Output is correct
11 Correct 167 ms 55652 KB Output is correct
12 Correct 58 ms 36308 KB Output is correct
13 Correct 123 ms 47996 KB Output is correct
14 Correct 17 ms 28868 KB Output is correct
15 Correct 22 ms 29264 KB Output is correct
16 Correct 510 ms 76380 KB Output is correct
17 Incorrect 17 ms 28756 KB Tree @(3, 3) appears more than once: for edges on positions 2 and 3
18 Halted 0 ms 0 KB -