Submission #829467

#	Time	Username	Problem	Language	Result	Execution time	Memory
829467		Abrar_Al_Samit	Fountain Parks (IOI21_parks)	C++17	15 / 100	643 ms	46036 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;

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

void trav(int v) {
    vis[v] = 1;
    for(int u : g[v]) if(!vis[u]) {
        trav(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;

    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))) {
                g[i].push_back(ft[{nx, ny}]);

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

                    if(j < 2) { //horizontal
                        a.push_back(x[i] + nx >> 1);
                        b.push_back(ny - 1);
                    } else { //vertical
                        if(x[i]==2) {
                            a.push_back(x[i] - 1);
                            b.push_back(y[i] + ny >> 1);
                        } else {
                            a.push_back(x[i] + 1);
                            b.push_back(y[i] + ny >> 1);
                        }
                    }
                }
            }
        }
    }
    trav(0);
    for(int i=0; i<n; ++i) if(!vis[i]) {
        return 0;
    }

    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:38:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |                         a.push_back(x[i] + nx >> 1);
parks.cpp:43:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |                             b.push_back(y[i] + ny >> 1);
parks.cpp:46:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |                             b.push_back(y[i] + ny >> 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