oj.uz

Submission #834490

# Submission time Handle Problem Language Result Execution time Memory
834490 2023-08-22T14:54:59 Z Abrar_Al_Samit Fountain Parks (IOI21_parks) C++17
15 / 100
 585 ms 57880 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 {
                if(ben.count(make_pair(x0+1, y0 + y1 >> 1))) return 0;
                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 {    
                if(ben.count(make_pair(x0 + x1 >> 1, y0 + 1))) return 0;
                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);
      |                             ~~~^~~~
parks.cpp:92:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 if(ben.count(make_pair(x0+1, y0 + y1 >> 1))) return 0;
      |                                              ~~~^~~~
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);
      |                             ~~~^~~~
parks.cpp:103:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |                 if(ben.count(make_pair(x0 + x1 >> 1, y0 + 1))) return 0;
      |                                        ~~~^~~~
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 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 209 ms 30688 KB Output is correct
10 Correct 14 ms 7680 KB Output is correct
11 Correct 78 ms 18896 KB Output is correct
12 Correct 19 ms 8924 KB Output is correct
13 Correct 38 ms 11072 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 206 ms 30020 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 209 ms 30688 KB Output is correct
10 Correct 14 ms 7680 KB Output is correct
11 Correct 78 ms 18896 KB Output is correct
12 Correct 19 ms 8924 KB Output is correct
13 Correct 38 ms 11072 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 206 ms 30020 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 571 ms 55460 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 4 ms 5332 KB Output is correct
26 Correct 5 ms 5332 KB Output is correct
27 Correct 6 ms 5460 KB Output is correct
28 Correct 173 ms 25252 KB Output is correct
29 Correct 301 ms 34932 KB Output is correct
30 Correct 447 ms 45628 KB Output is correct
31 Correct 575 ms 55184 KB Output is correct
32 Correct 2 ms 4948 KB Output is correct
33 Correct 2 ms 4948 KB Output is correct
34 Correct 2 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 2 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 2 ms 4948 KB Output is correct
41 Correct 2 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 5 ms 5332 KB Output is correct
45 Correct 222 ms 30208 KB Output is correct
46 Correct 348 ms 42284 KB Output is correct
47 Correct 377 ms 42300 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 209 ms 30688 KB Output is correct
10 Correct 14 ms 7680 KB Output is correct
11 Correct 78 ms 18896 KB Output is correct
12 Correct 19 ms 8924 KB Output is correct
13 Correct 38 ms 11072 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 206 ms 30020 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 571 ms 55460 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 4 ms 5332 KB Output is correct
26 Correct 5 ms 5332 KB Output is correct
27 Correct 6 ms 5460 KB Output is correct
28 Correct 173 ms 25252 KB Output is correct
29 Correct 301 ms 34932 KB Output is correct
30 Correct 447 ms 45628 KB Output is correct
31 Correct 575 ms 55184 KB Output is correct
32 Correct 2 ms 4948 KB Output is correct
33 Correct 2 ms 4948 KB Output is correct
34 Correct 2 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 2 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 2 ms 4948 KB Output is correct
41 Correct 2 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 5 ms 5332 KB Output is correct
45 Correct 222 ms 30208 KB Output is correct
46 Correct 348 ms 42284 KB Output is correct
47 Correct 377 ms 42300 KB Output is correct
48 Correct 2 ms 4948 KB Output is correct
49 Correct 2 ms 4948 KB Output is correct
50 Correct 2 ms 4948 KB Output is correct
51 Incorrect 2 ms 4948 KB Solution announced impossible, but it is possible.
52 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 209 ms 30688 KB Output is correct
10 Correct 14 ms 7680 KB Output is correct
11 Correct 78 ms 18896 KB Output is correct
12 Correct 19 ms 8924 KB Output is correct
13 Correct 38 ms 11072 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 206 ms 30020 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 583 ms 57880 KB Output is correct
21 Correct 523 ms 56916 KB Output is correct
22 Correct 585 ms 56560 KB Output is correct
23 Correct 434 ms 48564 KB Output is correct
24 Correct 277 ms 22348 KB Output is correct
25 Correct 497 ms 30240 KB Output is correct
26 Correct 447 ms 30168 KB Output is correct
27 Correct 581 ms 53520 KB Output is correct
28 Incorrect 484 ms 30356 KB Solution announced impossible, but it is possible.
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 209 ms 30688 KB Output is correct
10 Correct 14 ms 7680 KB Output is correct
11 Correct 78 ms 18896 KB Output is correct
12 Correct 19 ms 8924 KB Output is correct
13 Correct 38 ms 11072 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 206 ms 30020 KB Output is correct
17 Correct 559 ms 56944 KB Output is correct
18 Correct 537 ms 55856 KB Output is correct
19 Incorrect 480 ms 40984 KB Solution announced impossible, but it is possible.
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 209 ms 30688 KB Output is correct
10 Correct 14 ms 7680 KB Output is correct
11 Correct 78 ms 18896 KB Output is correct
12 Correct 19 ms 8924 KB Output is correct
13 Correct 38 ms 11072 KB Output is correct
14 Correct 4 ms 5076 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 206 ms 30020 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 571 ms 55460 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 4 ms 5332 KB Output is correct
26 Correct 5 ms 5332 KB Output is correct
27 Correct 6 ms 5460 KB Output is correct
28 Correct 173 ms 25252 KB Output is correct
29 Correct 301 ms 34932 KB Output is correct
30 Correct 447 ms 45628 KB Output is correct
31 Correct 575 ms 55184 KB Output is correct
32 Correct 2 ms 4948 KB Output is correct
33 Correct 2 ms 4948 KB Output is correct
34 Correct 2 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 2 ms 4948 KB Output is correct
39 Correct 2 ms 4948 KB Output is correct
40 Correct 2 ms 4948 KB Output is correct
41 Correct 2 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 5 ms 5332 KB Output is correct
45 Correct 222 ms 30208 KB Output is correct
46 Correct 348 ms 42284 KB Output is correct
47 Correct 377 ms 42300 KB Output is correct
48 Correct 2 ms 4948 KB Output is correct
49 Correct 2 ms 4948 KB Output is correct
50 Correct 2 ms 4948 KB Output is correct
51 Incorrect 2 ms 4948 KB Solution announced impossible, but it is possible.
52 Halted 0 ms 0 KB -