Submission #894824

#	Time	Username	Problem	Language	Result	Execution time	Memory
894824		Sir_Ahmed_Imran	Fountain Parks (IOI21_parks)	C++17	15 / 100	456 ms	56072 KiB

parks

                              ///~~~LOTA~~~///
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 200001
int siz[N];
int par[N];
int root(int v){
    if(!par[v]) return v;
    par[v]=root(par[v]);
    return par[v];
}
void merge(int v,int u){
    v=root(v);
    u=root(u);
    par[u]=v;
    siz[v]+=siz[u];
}
bool same(int v,int u){
    return (root(v)==root(u));
}
int construct_roads(vector<int> x,vector<int> y){
    map<pii,int> c,z;
    int n,m,o,p,q,r;
    n=x.size();
    vector<int> v,u,a,b;
    vector<pair<pii,int>> w;
    for(int i=0;i<n;i++){
        w.append({{y[i],x[i]},i+1});
        z[{x[i],y[i]}]=i+1;
        siz[i+1]=1;
    }
    sort(all(w));
    for(auto& i:w){
        q=i.ff.ff;
        p=i.ff.ss;
        r=z[{p-2,q}];
        if(r){
            if(!same(i.ss,r)){
                merge(i.ss,r);
                v.append(i.ss-1);
                u.append(r-1);
                if(!c[{p-1,q+1}]){
                    a.append(p-1);
                    b.append(q+1);
                    c[{p-1,q+1}]=1;
                }
                else if(!c[{p-1,q-1}]){
                    a.append(p-1);
                    b.append(q-1);
                    c[{p-1,q-1}]=1;
                }
                else return 0;
            }
        }
        r=z[{p,q-2}];
        if(r){
            if(!same(i.ss,r)){
                merge(i.ss,r);
                v.append(i.ss-1);
                u.append(r-1);
                if(!c[{p+1,q-1}]){
                    a.append(p+1);
                    b.append(q-1);
                    c[{p+1,q-1}]=1;
                }
                else if(!c[{p-1,q-1}]){
                    a.append(p-1);
                    b.append(q-1);
                    c[{p-1,q-1}]=1;
                }
                else return 0;
            }
        }
    }
    if(siz[root(1)]!=n) return 0;
    build(u,v,a,b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:31:11: warning: unused variable 'm' [-Wunused-variable]
   31 |     int n,m,o,p,q,r;
      |           ^
parks.cpp:31:13: warning: unused variable 'o' [-Wunused-variable]
   31 |     int n,m,o,p,q,r;
      |             ^

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