Submission #834489

#	Time	Username	Problem	Language	Result	Execution time	Memory
834489		Abrar_Al_Samit	Fountain Parks (IOI21_parks)	C++17	15 / 100	593 ms	85368 KiB

parks

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30