oj.uz

Submission #829739

# Submission time Handle Problem Language Result Execution time Memory
829739 2023-08-18T14:42:36 Z Abrar_Al_Samit Fountain Parks (IOI21_parks) C++17
5 / 100
 902 ms 89324 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;
    }
    for(int i=0; i<n; ++i) {
        for(int j=2; 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;

                if(!ben.count(make_pair(x[i] - 1, y[i] + ny >> 1))) {
                    ben[{x[i] - 1, y[i] + ny >> 1}] = 1;
                    a.push_back(x[i] - 1);
                    b.push_back(y[i] + ny >> 1);
                } else {
                    assert(!ben.count(make_pair(x[i] + 1, y[i] + ny >> 1)));
                    ben[{x[i] + 1, y[i] + ny >> 1}] = 1;
                    a.push_back(x[i] + 1);
                    b.push_back(y[i] + ny >> 1);
                }

                g[i].push_back(she);
                g[she].push_back(i);
                unite(i, she);
                u.push_back(i);
                v.push_back(she);
            }
        }
    }
    for(int i=0; i<n; ++i) {
        for(int j=0; j<2; ++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;

                if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
                    ben[{x[i] + nx >> 1, ny + 1}] = 1;
                    a.push_back(x[i] + nx >> 1);
                    b.push_back(ny + 1);
                } else {
                    assert(!ben.count(make_pair(x[i] + nx >> 1, ny - 1)));
                    ben[{x[i] + nx >> 1, ny - 1}] = 1;
                    a.push_back(x[i] + nx >> 1);
                    b.push_back(ny - 1);
                }

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

    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:50:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |                 if(!ben.count(make_pair(x[i] - 1, y[i] + ny >> 1))) {
parks.cpp:51:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |                     ben[{x[i] - 1, y[i] + ny >> 1}] = 1;
parks.cpp:53:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |                     b.push_back(y[i] + ny >> 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:55:64: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |                     assert(!ben.count(make_pair(x[i] + 1, y[i] + ny >> 1)));
parks.cpp:56:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |                     ben[{x[i] + 1, y[i] + ny >> 1}] = 1;
parks.cpp:58:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |                     b.push_back(y[i] + ny >> 1);
parks.cpp:76:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |                 if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
parks.cpp:77:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |                     ben[{x[i] + nx >> 1, ny + 1}] = 1;
parks.cpp:78:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |                     a.push_back(x[i] + nx >> 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:81:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |                     assert(!ben.count(make_pair(x[i] + nx >> 1, ny - 1)));
parks.cpp:82:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |                     ben[{x[i] + nx >> 1, ny - 1}] = 1;
parks.cpp:83:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |                     a.push_back(x[i] + nx >> 1);

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 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 220 ms 29368 KB Output is correct
10 Correct 13 ms 7636 KB Output is correct
11 Correct 76 ms 18224 KB Output is correct
12 Correct 19 ms 8916 KB Output is correct
13 Correct 50 ms 14172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 225 ms 28628 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 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 220 ms 29368 KB Output is correct
10 Correct 13 ms 7636 KB Output is correct
11 Correct 76 ms 18224 KB Output is correct
12 Correct 19 ms 8916 KB Output is correct
13 Correct 50 ms 14172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 225 ms 28628 KB Output is correct
17 Correct 2 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 2 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 Runtime error 495 ms 89324 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 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 220 ms 29368 KB Output is correct
10 Correct 13 ms 7636 KB Output is correct
11 Correct 76 ms 18224 KB Output is correct
12 Correct 19 ms 8916 KB Output is correct
13 Correct 50 ms 14172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 225 ms 28628 KB Output is correct
17 Correct 2 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 2 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 Runtime error 495 ms 89324 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 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 220 ms 29368 KB Output is correct
10 Correct 13 ms 7636 KB Output is correct
11 Correct 76 ms 18224 KB Output is correct
12 Correct 19 ms 8916 KB Output is correct
13 Correct 50 ms 14172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 225 ms 28628 KB Output is correct
17 Correct 2 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 770 ms 53972 KB Output is correct
21 Correct 742 ms 53248 KB Output is correct
22 Correct 760 ms 55420 KB Output is correct
23 Correct 563 ms 47444 KB Output is correct
24 Correct 287 ms 23932 KB Output is correct
25 Correct 788 ms 45868 KB Output is correct
26 Correct 636 ms 45864 KB Output is correct
27 Correct 748 ms 52248 KB Output is correct
28 Correct 819 ms 52216 KB Output is correct
29 Correct 902 ms 52120 KB Output is correct
30 Runtime error 187 ms 47052 KB Execution killed with signal 6
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 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 220 ms 29368 KB Output is correct
10 Correct 13 ms 7636 KB Output is correct
11 Correct 76 ms 18224 KB Output is correct
12 Correct 19 ms 8916 KB Output is correct
13 Correct 50 ms 14172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 225 ms 28628 KB Output is correct
17 Correct 622 ms 53316 KB Output is correct
18 Runtime error 340 ms 70032 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 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 220 ms 29368 KB Output is correct
10 Correct 13 ms 7636 KB Output is correct
11 Correct 76 ms 18224 KB Output is correct
12 Correct 19 ms 8916 KB Output is correct
13 Correct 50 ms 14172 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5332 KB Output is correct
16 Correct 225 ms 28628 KB Output is correct
17 Correct 2 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 2 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 Runtime error 495 ms 89324 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -