Submission #894854

#	Time	Username	Problem	Language	Result	Execution time	Memory
894854		Ghulam_Junaid	Fountain Parks (IOI21_parks)	C++17	15 / 100	496 ms	65512 KiB

parks

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

typedef pair<int, int> pii;

const int N = 2e5 + 10;
bool vis[N];
vector<int> g[N];

void dfs(int v){
    vis[v] = 1;
    for (int u : g[v])
        if (!vis[u]) dfs(u);
}

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
int construct_roads(vector<int> x, vector<int> y){
    int n = x.size();

    vector<int> edge[2], bench[2];
    vector<pii> vec;

    for (int i = 0; i < n; i ++)
        vec.push_back({x[i], y[i]});
    sort(vec.begin(), vec.end());

    map<pair<int, int>, int> ind;
    map<pair<int, int>, bool> done;
    for (int i=0; i<n; i++)
        ind[{x[i], y[i]}] = i;

    bool bad = 0;
    for (int i=0; i<n; i++){
        int px = vec[i].first;
        int py = vec[i].second;
        int cur = ind[{px, py}];

        if (ind.find({px, py + 2}) != ind.end()){
            edge[0].push_back(cur);
            edge[1].push_back(ind[{px, py + 2}]);
            g[cur].push_back(ind[{px, py + 2}]);
            g[ind[{px, py + 2}]].push_back(cur);

            if (!done[{px - 1, py + 1}]){
                done[{px - 1, py + 1}] = 1;
                bench[0].push_back(px - 1);
                bench[1].push_back(py + 1);
            }
            else if (!done[{px + 1, py + 1}]){
                done[{px + 1, py + 1}] = 1;
                bench[0].push_back(px + 1);
                bench[1].push_back(py + 1);
            }
            else
                bad = 1;
        }
        if (ind.find({px + 2, py}) != ind.end()){
            edge[0].push_back(cur);
            edge[1].push_back(ind[{px + 2, py}]);
            g[cur].push_back(ind[{px + 2, py}]);
            g[ind[{px + 2, py}]].push_back(cur);   

            if (!done[{px + 1, py - 1}]){
                done[{px + 1, py - 1}] = 1;
                bench[0].push_back(px + 1);
                bench[1].push_back(py - 1);
            }
            else if (!done[{px + 1, py + 1}]){
                done[{px + 1, py + 1}] = 1;
                bench[0].push_back(px + 1);
                bench[1].push_back(py + 1);
            }
            else
                bad = 1;
        }
    }

    dfs(0);

    for (int v = 0; v < n; v ++)
        if (!vis[v]) bad = 1;

    if (bad)
        return 0;

    build(edge[0], edge[1], bench[0], bench[1]);
    return 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