oj.uz

Submission #829514

# Submission time Handle Problem Language Result Execution time Memory
829514 2023-08-18T11:51:18 Z Abrar_Al_Samit Fountain Parks (IOI21_parks) C++17
0 / 100
 212 ms 17268 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=0; j<4; ++j) {
            int nx = x[i] + dx[j], ny = y[i] + dy[j];
            if(ft.count(make_pair(nx, ny))) {
                if(find(i) == find(ft[{nx, ny}])) continue;

                

                if(j < 2) { //horizontal
                    if((x[i] + nx >> 1) < 4) {
                        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 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(0);
                    } else {
                        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 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(0);                    
                    }
                } else { //vertical
                    if(x[i]==2) {
                        a.push_back(x[i] - 1);
                        b.push_back(y[i] + ny >> 1);
                    } else if(x[i]==6) {
                        a.push_back(x[i] + 1);
                        b.push_back(y[i] + ny >> 1);
                    } else {
                        continue;
                    }
                }
                g[i].push_back(ft[{nx, ny}]);
                unite(i, ft[{nx, ny}]);
                u.push_back(i);
                v.push_back(ft[{nx, ny}]);
            }
        }
    }
    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))) {
                if(find(i) == find(ft[{nx, ny}])) continue;

                g[i].push_back(ft[{nx, ny}]);
                unite(i, ft[{nx, ny}]);
                u.push_back(i);
                v.push_back(ft[{nx, ny}]);

                if(!ben.count(make_pair(nx-1, y[i] + ny >> 1))) {
                    ben[{nx-1, y[i] + ny >> 1}] = 1;
                    a.push_back(nx-1);
                    b.push_back(y[i] + ny >> 1);
                } else if(!ben.count(make_pair(nx+1, y[i] + ny >> 1))) {
                    ben[{nx+1, y[i] + ny >> 1}] = 1;
                    a.push_back(nx+1);
                    b.push_back(y[i] + ny >> 1);
                } else assert(0);
            }
        }
    }
    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:52:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |                     if((x[i] + nx >> 1) < 4) {
parks.cpp:53:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |                         if(!ben.count(make_pair(x[i] + nx >> 1, ny - 1))) {
parks.cpp:54:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |                             ben[{x[i] + nx >> 1, ny - 1}] = 1;
parks.cpp:55:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |                             a.push_back(x[i] + nx >> 1);
parks.cpp:57:61: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |                         } else if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
parks.cpp:58:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |                             ben[{x[i] + nx >> 1, ny + 1}] = 1;
parks.cpp:59:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |                             a.push_back(x[i] + nx >> 1);
parks.cpp:64:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |                         if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
parks.cpp:65:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |                             ben[{x[i] + nx >> 1, ny + 1}] = 1;
parks.cpp:66:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |                             a.push_back(x[i] + nx >> 1);
parks.cpp:69:61: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |                         } else if(!ben.count(make_pair(x[i] + nx >> 1, ny - 1))) {
parks.cpp:70:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |                             ben[{x[i] + nx >> 1, ny - 1}] = 1;
parks.cpp:71:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |                             a.push_back(x[i] + nx >> 1);
parks.cpp:78:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |                         b.push_back(y[i] + ny >> 1);
parks.cpp:81:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |                         b.push_back(y[i] + ny >> 1);
parks.cpp:104:52: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |                 if(!ben.count(make_pair(nx-1, y[i] + ny >> 1))) {
parks.cpp:105:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |                     ben[{nx-1, y[i] + ny >> 1}] = 1;
parks.cpp:107:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |                     b.push_back(y[i] + ny >> 1);
parks.cpp:108:59: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |                 } else if(!ben.count(make_pair(nx+1, y[i] + ny >> 1))) {
parks.cpp:109:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |                     ben[{nx+1, y[i] + ny >> 1}] = 1;
parks.cpp:111:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |                     b.push_back(y[i] + ny >> 1);

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 212 ms 17268 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 212 ms 17268 KB Solution announced impossible, but it is possible.
10 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 212 ms 17268 KB Solution announced impossible, but it is possible.
10 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 212 ms 17268 KB Solution announced impossible, but it is possible.
10 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 212 ms 17268 KB Solution announced impossible, but it is possible.
10 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 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Incorrect 212 ms 17268 KB Solution announced impossible, but it is possible.
10 Halted 0 ms 0 KB -