oj.uz

Submission #834489

# Submission time Handle Problem Language Result Execution time Memory
834489 2023-08-22T14:53:44 Z Abrar_Al_Samit Fountain Parks (IOI21_parks) C++17
15 / 100
 593 ms 85368 KB 
#include <bits/stdc++.h>
#include "parks.h"
using namespace std;

const int nax = 200000;
vector<int>g[nax];
bool vis[nax];
int par[nax], sz[nax];

void trav(int v) {
    vis[v] = 1;
    for(int u : g[v]) if(!vis[u]) {
        trav(u);
    }
}

int find(int v) {
    return par[v] = (v==par[v]) ? v : find(par[v]);
}
void unite(int u, int v) {
    u = find(u), v = find(v);
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
}
int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    map<pair<int,int>, int>ft;
    for(int i=0; i<n; ++i) {
        ft[{x[i], y[i]}] = i;
    }

    int dx[] = {2, -2, 0, 0};
    int dy[] = {0, 0, 2, -2};

    vector<int>u, v, a, b;

    map<pair<int,int>, int>ben;

    for(int i=0; i<n; ++i) {
        par[i] = i, sz[i] = 1;
    }

    vector<pair<int,int>>eds;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<4; ++j) {
            int nx = x[i] + dx[j], ny = y[i] + dy[j];
            if(ft.count(make_pair(nx, ny))) {
                int she = ft[{nx, ny}];
                if(find(i) == find(she)) continue;

                g[i].push_back(she);
                g[she].push_back(i);
                unite(i, she);
                eds.emplace_back(i, she);
            }
        }
    }
    trav(0);
    for(int i=0; i<n; ++i) if(!vis[i]) {
        return 0;
    }



    for(int i=0; i<n-1; ++i) {
        auto [me, she] = eds[i];
        int x0 = x[me], y0 = y[me], x1 = x[she], y1 = y[she];
        if(x0 > x1) swap(eds[i].first, eds[i].second);
    }

    sort(eds.begin(), eds.end(), [&] (auto p, auto q) {
        if(x[p.first]==x[q.first]) {
            return max(y[p.first], y[p.second]) > max(y[q.first], y[q.second]);
        }
        return x[p.first] < x[q.first];
    });


    for(auto [me, she] : eds) {
        u.push_back(me);
        v.push_back(she);

        int x0 = x[me], y0 = y[me], x1 = x[she], y1 = y[she];

        if(x0==x1) { //vertical
            if(!ben.count(make_pair(x0-1, y0 + y1 >> 1))) {
                ben[{x0-1, y0 + y1 >> 1}] = 1;
                a.push_back(x0-1);
                b.push_back(y0 + y1 >> 1);
            } else {
                assert(!ben.count(make_pair(x0+1, y0 + y1 >> 1)));
                ben[{x0+1, y0 + y1 >> 1}] = 1;
                a.push_back(x0+1);
                b.push_back(y0 + y1 >> 1);
            }
        } else {
            if(!ben.count(make_pair(x0 + x1 >> 1, y0 - 1))) {
                ben[{x0 + x1 >> 1, y0 - 1}] = 1;
                a.push_back(x0 + x1 >> 1);
                b.push_back(y0 - 1);
            } else {    
                assert(!ben.count(make_pair(x0 + x1 >> 1, y0 + 1)));
                ben[{x0 + x1 >> 1, y0 + 1}] = 1;
                a.push_back(x0 + x1 >> 1);
                b.push_back(y0 + 1);
            }
        }
    }
    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:68:25: warning: unused variable 'y0' [-Wunused-variable]
   68 |         int x0 = x[me], y0 = y[me], x1 = x[she], y1 = y[she];
      |                         ^~
parks.cpp:68:50: warning: unused variable 'y1' [-Wunused-variable]
   68 |         int x0 = x[me], y0 = y[me], x1 = x[she], y1 = y[she];
      |                                                  ^~
parks.cpp:87:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |             if(!ben.count(make_pair(x0-1, y0 + y1 >> 1))) {
      |                                           ~~~^~~~
parks.cpp:88:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |                 ben[{x0-1, y0 + y1 >> 1}] = 1;
      |                            ~~~^~~~
parks.cpp:90:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |                 b.push_back(y0 + y1 >> 1);
      |                             ~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from parks.cpp:1:
parks.cpp:92:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 assert(!ben.count(make_pair(x0+1, y0 + y1 >> 1)));
      |                                                   ~~~^~~~
parks.cpp:93:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |                 ben[{x0+1, y0 + y1 >> 1}] = 1;
      |                            ~~~^~~~
parks.cpp:95:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |                 b.push_back(y0 + y1 >> 1);
      |                             ~~~^~~~
parks.cpp:98:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             if(!ben.count(make_pair(x0 + x1 >> 1, y0 - 1))) {
      |                                     ~~~^~~~
parks.cpp:99:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |                 ben[{x0 + x1 >> 1, y0 - 1}] = 1;
      |                      ~~~^~~~
parks.cpp:100:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |                 a.push_back(x0 + x1 >> 1);
      |                             ~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from parks.cpp:1:
parks.cpp:103:48: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |                 assert(!ben.count(make_pair(x0 + x1 >> 1, y0 + 1)));
      |                                             ~~~^~~~
parks.cpp:104:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |                 ben[{x0 + x1 >> 1, y0 + 1}] = 1;
      |                      ~~~^~~~
parks.cpp:105:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |                 a.push_back(x0 + x1 >> 1);
      |                             ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 2 ms 5008 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 206 ms 31572 KB Output is correct
10 Correct 14 ms 7688 KB Output is correct
11 Correct 75 ms 19252 KB Output is correct
12 Correct 20 ms 9052 KB Output is correct
13 Correct 39 ms 11368 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 210 ms 30880 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 2 ms 5008 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 206 ms 31572 KB Output is correct
10 Correct 14 ms 7688 KB Output is correct
11 Correct 75 ms 19252 KB Output is correct
12 Correct 20 ms 9052 KB Output is correct
13 Correct 39 ms 11368 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 210 ms 30880 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 5008 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 5012 KB Output is correct
22 Correct 2 ms 5012 KB Output is correct
23 Correct 564 ms 57112 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 4 ms 5272 KB Output is correct
26 Correct 6 ms 5332 KB Output is correct
27 Correct 9 ms 5544 KB Output is correct
28 Correct 176 ms 25844 KB Output is correct
29 Correct 294 ms 35956 KB Output is correct
30 Correct 405 ms 46988 KB Output is correct
31 Correct 593 ms 56888 KB Output is correct
32 Correct 3 ms 4948 KB Output is correct
33 Correct 2 ms 4948 KB Output is correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 3 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 3 ms 4948 KB Output is correct
41 Correct 3 ms 4948 KB Output is correct
42 Correct 2 ms 4948 KB Output is correct
43 Correct 4 ms 5204 KB Output is correct
44 Correct 6 ms 5316 KB Output is correct
45 Correct 233 ms 31276 KB Output is correct
46 Correct 357 ms 43500 KB Output is correct
47 Correct 366 ms 43280 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 2 ms 5008 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 206 ms 31572 KB Output is correct
10 Correct 14 ms 7688 KB Output is correct
11 Correct 75 ms 19252 KB Output is correct
12 Correct 20 ms 9052 KB Output is correct
13 Correct 39 ms 11368 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 210 ms 30880 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 5008 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 5012 KB Output is correct
22 Correct 2 ms 5012 KB Output is correct
23 Correct 564 ms 57112 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 4 ms 5272 KB Output is correct
26 Correct 6 ms 5332 KB Output is correct
27 Correct 9 ms 5544 KB Output is correct
28 Correct 176 ms 25844 KB Output is correct
29 Correct 294 ms 35956 KB Output is correct
30 Correct 405 ms 46988 KB Output is correct
31 Correct 593 ms 56888 KB Output is correct
32 Correct 3 ms 4948 KB Output is correct
33 Correct 2 ms 4948 KB Output is correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 3 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 3 ms 4948 KB Output is correct
41 Correct 3 ms 4948 KB Output is correct
42 Correct 2 ms 4948 KB Output is correct
43 Correct 4 ms 5204 KB Output is correct
44 Correct 6 ms 5316 KB Output is correct
45 Correct 233 ms 31276 KB Output is correct
46 Correct 357 ms 43500 KB Output is correct
47 Correct 366 ms 43280 KB Output is correct
48 Correct 2 ms 4948 KB Output is correct
49 Correct 2 ms 4948 KB Output is correct
50 Correct 3 ms 4948 KB Output is correct
51 Runtime error 7 ms 9940 KB Execution killed with signal 6
52 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 2 ms 5008 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 206 ms 31572 KB Output is correct
10 Correct 14 ms 7688 KB Output is correct
11 Correct 75 ms 19252 KB Output is correct
12 Correct 20 ms 9052 KB Output is correct
13 Correct 39 ms 11368 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 210 ms 30880 KB Output is correct
17 Correct 2 ms 5012 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 585 ms 60328 KB Output is correct
21 Correct 558 ms 59212 KB Output is correct
22 Correct 543 ms 58880 KB Output is correct
23 Correct 448 ms 50392 KB Output is correct
24 Correct 269 ms 23844 KB Output is correct
25 Correct 453 ms 31744 KB Output is correct
26 Correct 418 ms 31784 KB Output is correct
27 Correct 534 ms 55028 KB Output is correct
28 Runtime error 461 ms 62952 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 2 ms 5008 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 206 ms 31572 KB Output is correct
10 Correct 14 ms 7688 KB Output is correct
11 Correct 75 ms 19252 KB Output is correct
12 Correct 20 ms 9052 KB Output is correct
13 Correct 39 ms 11368 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 210 ms 30880 KB Output is correct
17 Correct 524 ms 59004 KB Output is correct
18 Correct 520 ms 57964 KB Output is correct
19 Runtime error 510 ms 85368 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5012 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 2 ms 5012 KB Output is correct
6 Correct 2 ms 5008 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 206 ms 31572 KB Output is correct
10 Correct 14 ms 7688 KB Output is correct
11 Correct 75 ms 19252 KB Output is correct
12 Correct 20 ms 9052 KB Output is correct
13 Correct 39 ms 11368 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 210 ms 30880 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 5008 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 2 ms 5012 KB Output is correct
22 Correct 2 ms 5012 KB Output is correct
23 Correct 564 ms 57112 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 4 ms 5272 KB Output is correct
26 Correct 6 ms 5332 KB Output is correct
27 Correct 9 ms 5544 KB Output is correct
28 Correct 176 ms 25844 KB Output is correct
29 Correct 294 ms 35956 KB Output is correct
30 Correct 405 ms 46988 KB Output is correct
31 Correct 593 ms 56888 KB Output is correct
32 Correct 3 ms 4948 KB Output is correct
33 Correct 2 ms 4948 KB Output is correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 2 ms 4948 KB Output is correct
36 Correct 2 ms 4948 KB Output is correct
37 Correct 2 ms 4948 KB Output is correct
38 Correct 3 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 3 ms 4948 KB Output is correct
41 Correct 3 ms 4948 KB Output is correct
42 Correct 2 ms 4948 KB Output is correct
43 Correct 4 ms 5204 KB Output is correct
44 Correct 6 ms 5316 KB Output is correct
45 Correct 233 ms 31276 KB Output is correct
46 Correct 357 ms 43500 KB Output is correct
47 Correct 366 ms 43280 KB Output is correct
48 Correct 2 ms 4948 KB Output is correct
49 Correct 2 ms 4948 KB Output is correct
50 Correct 3 ms 4948 KB Output is correct
51 Runtime error 7 ms 9940 KB Execution killed with signal 6
52 Halted 0 ms 0 KB -