oj.uz

Submission #796553

# Submission time Handle Problem Language Result Execution time Memory
796553 2023-07-28T13:51:46 Z Khizri Fountain Parks (IOI21_parks) C++17
0 / 100
 3 ms 4948 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,x[mxn],y[mxn],p[mxn],sz[mxn];
int ax[4]={1,1,-1,-1};
int ay[4]={-1,1,1,-1};
vector<pair<pii,int>>vt;
map<pii,int>mp;
vector<int>adj[mxn];
int fnd(int u){
    if(p[u]==u) return u;
    return p[u]=fnd(p[u]);
}
void Union(int u,int v){
    u=fnd(u);
    v=fnd(v);
    if(u!=v){
        if(sz[u]>sz[v]) swap(u,v);
        sz[u]+=sz[v];
        p[v]=u;
    }
}
bool cmp(pair<pii,int> a,pair<pii,int> b){
    return a.F.S<b.F.S;
}
int construct_roads(vector<int> xx, vector<int> yy) {
    n=xx.size();
    if(n==1){
        build({},{},{},{});
        return 1;
    }
    for(int i=0;i<n;i++){
        vt.pb({{xx[i],yy[i]},i+1});
        mp[{xx[i],yy[i]}]=i+1;
        x[i+1]=xx[i];
        y[i+1]=yy[i];
    }
    set<pii>st;
    for(int i=1;i<=n;i++){
        p[i]=i;
        sz[i]=1;
    }
    vector<int>idxl,idxr,posl,posr;
    sort(all(vt));
    for(int i=1;i<n;i++){
        if(abs(vt[i].F.F-vt[i-1].F.F)+abs(vt[i].F.S-vt[i-1].F.S)==2){
            Union(vt[i-1].S,vt[i].S);
        }
    }
    sort(all(vt),cmp);
    for(int i=1;i<n;i++){
        if(abs(vt[i].F.F-vt[i-1].F.F)+abs(vt[i].F.S-vt[i-1].F.S)==2){
            Union(vt[i-1].S,vt[i].S);
        }
    }
    if(sz[fnd(1)]!=n) return 0;
    for(int i=1;i<=n;i++){
        int l=x[i],r=y[i];
        int node=mp[{l,r}];
        int a=l+2,b=r;
        int c=l,d=r+2;
        int color=((l+r)/2)%2;
        int idx=mp[{a,b}];
        int idx2=mp[{c,d}];
        if(idx){
            int pos1=(l+a)/2,pos2=(r+b)/2;
            if(color){
                pos2++;
            }
            else{
                pos2--;
            }
            if(!st.count({pos1,pos2})){
                idxl.pb(node-1);
                idxr.pb(idx-1);
                posl.pb(pos1);
                posr.pb(pos2);
                st.insert({pos1,pos2});
            }
        }
        if(idx2){
            int pos1=(l+c)/2,pos2=(r+d)/2;
            if(color){
                pos1--;
            }
            else{
                pos1++;
            }
            if(!st.count({pos1,pos2})){
                idxl.pb(node-1);
                idxr.pb(idx-1);
                posl.pb(pos1);
                posr.pb(pos2);
                st.insert({pos1,pos2});
            }
        }
    }
    build(idxl,idxr,posl,posr);
    return 1;
}
/*
 { g++ parks.cpp grader.cpp } ; if ($?) { .\a.exe }
9
2 2
2 4
2 6
4 2
4 4
4 6
6 2
6 4
6 6
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Integer parameter [name=v[j]] equals to -1, violates the range [0, 1]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Integer parameter [name=v[j]] equals to -1, violates the range [0, 1]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Integer parameter [name=v[j]] equals to -1, violates the range [0, 1]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Integer parameter [name=v[j]] equals to -1, violates the range [0, 1]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Integer parameter [name=v[j]] equals to -1, violates the range [0, 1]
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Integer parameter [name=v[j]] equals to -1, violates the range [0, 1]
3 Halted 0 ms 0 KB -