제출 #435705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435705		Mazaalai	분수 공원 (IOI21_parks)	C++17	0 / 100	1 ms	972 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;
// vector <int> a1, b1, c1, d1;
// void build(vector <int> a, vector <int> b, vector <int> c, vector <int> d) {
//     a1 = a;
//     b1 = b;
//     c1 = c;
//     d1 = d;
// }
const int N = 2e5 + 5;
int n;
vector <vector <int> > pos;
vector <int> a2, b2, c2, d2, par(N);
map <pair <int, int> , int> fIdx;
set <pair <int, int> > used;
int find(int a) {
    if (par[a] == a) return a;
    return par[a] = find(par[a]);   
}
bool merge(int a, int b) {
    a = find(a), b = find(b);
    cout << "HERE\n";
    if (a == b) return 0;
    par[b] = a;
    return 1;
}
void connect(pair <int, int> pt, int i, int j) {
    if (used.count(pt)) return;
    used.insert(pt);
    merge(i, j);
    a2.push_back(i);
    b2.push_back(j);
    c2.push_back(pt.first);
    d2.push_back(pt.second);
}
void xEdge(int x, int y) {
    int X = x+1, Y = y + ((x+y)& 2 ? 1 : -1);
    connect({X, Y}, fIdx[{x, y}], fIdx[{x+2, y}]);
}
void yEdge(int x, int y) {
    int X = x + ((x+y)& 2 ? 1 : -1), Y = y+1;
    connect({X, Y}, fIdx[{x, y}], fIdx[{x, y+2}]);
}
bool custom(vector<int>&a, vector<int>&b) {
    return a < b;
}
int construct_roads(vector<int> X, vector<int> Y) {
    n = X.size();
    for (int i = 0; i < n; i++) 
        pos.push_back({X[i], Y[i], i});
    for (int i = 0; i < N; i++) par[i] = i;
    sort(pos.begin(), pos.end(), custom);
    for (int i = 0; i < n; i++) {
        int id = pos[i][2];
        pair <int, int> cur = {pos[i][0], pos[i][1]};
        fIdx[cur] = id;
        if (fIdx.count({cur.first-2, cur.second})) xEdge(cur.first-2, cur.second);
        if (fIdx.count({cur.first, cur.second-2})) yEdge(cur.first, cur.second-2);
    }
    int source = find(0);
    // for (int i = 0; i < n; i++) {
    //     cout << i << ' ' << find(i) << '\n';
    // }
    for (int i = 1; i < n; i++) {
        if (source != find(i)) return 0;
    }
    build(a2, b2, c2, d2);
    return 1;
}

// int main() {
//     int n, a, b;
//     freopen("in.txt", "r", stdin);
//     cin >> n;
//     vector <int> x, y;
//     for (int i = 0; i < n; i++) {
//         cin >> a >> b;
//         x.push_back(a);
//         y.push_back(b);
//     }
//     int val = construct_roads(x, y);
//     cout << val << '\n';
//     cout << a1.size() << '\n';
//     for (int i = 0; i < a1.size(); i++) {
//         cout << a1[i] << ' ' << b1[i] << ' ' << c1[i] << ' ' << d1[i] << '\n';
//     }
// }

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