oj.uz

Submission #1033982

# Submission time Handle Problem Language Result Execution time Memory
1033982 2024-07-25T08:22:01 Z hotboy2703 Fountain Parks (IOI21_parks) C++17
0 / 100
 0 ms 348 KB 
#include "parks.h"

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
struct point{
    ll x,y,id;
    point(ll x1 = 0,ll y1 = 0,ll id1 = 0):x(x1),y(y1),id(id1){}
    bool operator < (const point &p)const {
        return MP(x,y) < MP(p.x,p.y);
    }
};
const ll MAXN = 2e5+100;
ll dsu[MAXN];
ll f(ll x){
    if (dsu[x] < 0)return x;
    return (dsu[x] = f(dsu[x]));
}
bool join(ll x,ll y){
    x = f(x),y = f(y);
    if (x==y)return 0;
    dsu[x] += dsu[y];
    dsu[y] = x;
    return 1;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    ll n = sz(x);
    vector <point> a(n);
    
    for (ll i = 0;i < n;i ++){
        dsu[i] = -1;
        a[i] = {x[i],y[i],i};
    }
    sort(a.begin(),a.end());
    vector <int> U, V, A, B;
    set <pll> bench;
    auto add = [&](ll u,ll v, ll x,ll y){
        cout<<u<<' '<<v<<endl;
        if (join(u,v)==0)return;
        U.push_back(u);
        V.push_back(v);
        A.push_back(x);
        B.push_back(y);
        bench.insert(MP(x,y));
    };
    auto id = [&](pll x){
        auto tmp = lower_bound(a.begin(),a.end(),point(x.fi,x.se,0));
        if (tmp != a.end() && (*tmp).x==x.fi&&(*tmp).y==x.se)return (*tmp).id;
        else return -1;
    };
    for (ll i = 0;i < n;i ++){
        // cout<<i<<endl;
        if (((a[i].x + a[i].y)/2)&1){
            if (bench.find(MP(a[i].x + 1,a[i].y - 1)) == bench.end() && id(MP(a[i].x,a[i].y-2)) != -1){
                add(a[i].id,id(MP(a[i].x,a[i].y-2)),a[i].x+1,a[i].y-1);
            }
            if (bench.find(MP(a[i].x - 1,a[i].y - 1)) == bench.end() && id(MP(a[i].x-2,a[i].y)) != -1){
                add(a[i].id,id(MP(a[i].x-2,a[i].y)),a[i].x-1,a[i].y-1);
            }
        }
        else{
            // cout<<i<<endl;
            if (bench.find(MP(a[i].x - 1,a[i].y - 1)) == bench.end() && id(MP(a[i].x,a[i].y-2)) != -1){
                add(a[i].id,id(MP(a[i].x,a[i].y-2)),a[i].x-1,a[i].y-1);
            }
            if (bench.find(MP(a[i].x - 1,a[i].y + 1)) == bench.end() && id(MP(a[i].x-2,a[i].y)) != -1){
                add(a[i].id,id(MP(a[i].x-2,a[i].y)),a[i].x-1,a[i].y+1);
            }
        }
    }
    {
        vector <vector <ll > > g(n);
        for (ll i = 0;i < sz(U);i ++){
            g[U[i]].push_back(V[i]);
            g[V[i]].push_back(U[i]);
        }
        vector <bool> in(n);
        queue <ll> q;
        q.push(0);
        in[0] = 1;
        while (!q.empty()){
            ll u = q.front();
            q.pop();
            for (auto v:g[u]){
                if (!in[v]){
                    in[v] = 1;
                    q.push(v);
                }
            }
        }
        for (ll i = 0;i < n;i ++)if (!in[i])return 0;
        build(U, V, A, B);
        return 1;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Possible tampering with the output
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Possible tampering with the output
3 Halted 0 ms 0 KB -