Submission #1188655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188655		yellowtoad	Fountain Parks (IOI21_parks)	C++20	100 / 100	459 ms	76448 KiB

parks

#include "parks.h"
#include <iostream>
#include <map>
#include <algorithm>
#define f first
#define s second
using namespace std;

int n, vis[200010];
vector<pair<int,int>> pt;
map<pair<int,int>,int> mp, hv;
vector<int> edge[200010];

void dfs(int u) {
    vis[u] = 1;
    for (int i = 0; i < edge[u].size(); i++) if (!vis[edge[u][i]]) dfs(edge[u][i]);
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    n = x.size();
    for (int i = 0; i < n; i++) pt.push_back({x[i],y[i]}), mp[{x[i],y[i]}] = i+1;
    sort(pt.begin(),pt.end());
    vector<int> u, v, a, b;
    for (int i = 0; i < n; i++) {
        if (mp[{pt[i].f,pt[i].s-2}]) {
            if ((pt[i].f+pt[i].s)%4 == 0) {
                hv[{pt[i].f,pt[i].s}] = 1;
                u.push_back(mp[{pt[i].f,pt[i].s-2}]-1);
                v.push_back(mp[{pt[i].f,pt[i].s}]-1);
                a.push_back(pt[i].f+1);
                b.push_back(pt[i].s-1);
                edge[mp[{pt[i].f,pt[i].s-2}]].push_back(mp[{pt[i].f,pt[i].s}]);
                edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s-2}]);
            } else if (hv[{pt[i].f-2,pt[i].s}] == 0) {
                u.push_back(mp[{pt[i].f,pt[i].s-2}]-1);
                v.push_back(mp[{pt[i].f,pt[i].s}]-1);
                a.push_back(pt[i].f-1);
                b.push_back(pt[i].s-1);
                edge[mp[{pt[i].f,pt[i].s-2}]].push_back(mp[{pt[i].f,pt[i].s}]);
                edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s-2}]);
            }
        }
        if (mp[{pt[i].f-2,pt[i].s}]) {
            if ((pt[i].f+pt[i].s)%4 == 2) {
                hv[{pt[i].f,pt[i].s}] = 1;
                u.push_back(mp[{pt[i].f-2,pt[i].s}]-1);
                v.push_back(mp[{pt[i].f,pt[i].s}]-1);
                a.push_back(pt[i].f-1);
                b.push_back(pt[i].s+1);
                edge[mp[{pt[i].f-2,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s}]);
                edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f-2,pt[i].s}]);
            } else if (hv[{pt[i].f,pt[i].s-2}] == 0) {
                u.push_back(mp[{pt[i].f-2,pt[i].s}]-1);
                v.push_back(mp[{pt[i].f,pt[i].s}]-1);
                a.push_back(pt[i].f-1);
                b.push_back(pt[i].s-1);
                edge[mp[{pt[i].f-2,pt[i].s}]].push_back(mp[{pt[i].f,pt[i].s}]);
                edge[mp[{pt[i].f,pt[i].s}]].push_back(mp[{pt[i].f-2,pt[i].s}]);
            }
        }
    }
    dfs(1);
    for (int i = 1; i <= n; i++) if (!vis[i]) return 0;
    build(u,v,a,b);
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30