oj.uz

Submission #438831

# Submission time Handle Problem Language Result Execution time Memory
438831 2021-06-28T17:20:27 Z teehandsome Fountain Parks (IOI21_parks) C++17
0 / 100
 86 ms 14004 KB 
#include "parks.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF (int) 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;

template<typename T>
using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename AA,typename BB>
void _print(vector<pair<AA,BB>> x) {cerr<<"["; int cnt_temp12=0;
    for(auto e:x) {
            if(cnt_temp12) cerr<<", ";
            cerr<<"{"<<e.first<<","<<e.second<<"}"; ++cnt_temp12;} cerr<<"]";
    }
template<typename AA,typename BB>
void _print(pair<AA,BB> x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(vector<T> x) {cerr<<"{"; int cnt_temp12=0;
    for(auto e:x) {
            if(cnt_temp12) cerr<<",";
            cerr<<e; ++cnt_temp12;
    }cerr<<"}";
}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<" \"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\" ",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//int rnglr(int l,int r) {return rng()%(r-l+1)+l;}

struct dt {
    int x,y,idx;
    bool operator<(const dt &r) {
        return y<r.y;
    }
};

const int mxn = 2e5+100;
int n;
int flag[7][mxn];
vector<int> par;

int dm[4] = {-2,0,2,0};
int dn[4] = {0,2,0,-2};

bool valid(int M,int N) {
    if(M<=0 or N<=0 or M>4) return false;
    return flag[M][N]>=0;
}

int findp(int x) {
    if(par[x] == x) return x;
    return par[x] = findp(par[x]);
}

void unionset(int u,int v) {
    int U = findp(u), V = findp(v);
    par[U] = V;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
        build({}, {}, {}, {});
        return 1;
    }

    n = x.size();
    par.resize(n);
    for(int i=0;i<n;i++) par[i] = i;
    vector<dt> ar;
    for(int i=0;i<7;i++) fill(flag[i],flag[i]+mxn,-1);

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

    for(int i=0;i<n;i++) {
        flag[x[i]][y[i]] = i;
    }

    vector<int> u,v,a,b;

    for(int i=0;i<n;i++) {

        int X = x[i], Y = y[i];
        for(int j=0;j<4;j++) {
            int XX = X+dm[j], YY = Y+dn[j];
            if(valid(XX,YY)) {
                int i2 = flag[XX][YY];
                if(i>i2) continue;
//                debug(i,i2);
                u.push_back(ar[i].idx);
                v.push_back(ar[i2].idx);
                unionset(i,i2);

                if(X==2) {
                    if(XX==2) a.push_back(1),b.push_back(min(Y,YY)+1);
                    else a.push_back(3),b.push_back(min(Y,YY)+1);
                }
                else {
                    // X=4
                    if(XX==2) a.push_back(3),b.push_back(min(Y,YY)+1);
                    else a.push_back(5), b.push_back(min(Y,YY)+1);
                }
            }
//            debug(u);
//            debug(v);
//            debug(a);
//            debug(b);
        }
    }
//    debug(u);
//    debug(v);
//    debug(a);
//    debug(b);

    set<int> par_list;
    for(int i=0;i<n;i++) {
        int temp = findp(i);
        par_list.insert(temp);
    }
    if(par_list.size()!=1) return 0;
    build(u,v,a,b);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 3 ms 5708 KB Output is correct
9 Incorrect 86 ms 14004 KB Pair u[0]=13952 @(2, 2) and v[0]=99571 @(2, 173098) does not form a valid edge (distance != 2)
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 3 ms 5708 KB Output is correct
9 Incorrect 86 ms 14004 KB Pair u[0]=13952 @(2, 2) and v[0]=99571 @(2, 173098) does not form a valid edge (distance != 2)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 3 ms 5708 KB Output is correct
9 Incorrect 86 ms 14004 KB Pair u[0]=13952 @(2, 2) and v[0]=99571 @(2, 173098) does not form a valid edge (distance != 2)
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 3 ms 5708 KB Output is correct
9 Incorrect 86 ms 14004 KB Pair u[0]=13952 @(2, 2) and v[0]=99571 @(2, 173098) does not form a valid edge (distance != 2)
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 3 ms 5708 KB Output is correct
9 Incorrect 86 ms 14004 KB Pair u[0]=13952 @(2, 2) and v[0]=99571 @(2, 173098) does not form a valid edge (distance != 2)
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5708 KB Output is correct
7 Correct 3 ms 5708 KB Output is correct
8 Correct 3 ms 5708 KB Output is correct
9 Incorrect 86 ms 14004 KB Pair u[0]=13952 @(2, 2) and v[0]=99571 @(2, 173098) does not form a valid edge (distance != 2)
10 Halted 0 ms 0 KB -