oj.uz

Submission #1049856

# Submission time Handle Problem Language Result Execution time Memory
1049856 2024-08-09T05:47:01 Z nisanduu Fountain Parks (IOI21_parks) C++17
0 / 100
 238 ms 39984 KB 
#include "parks.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;

class Disjoint{
    vector<int> parent,sz;
    public:
        Disjoint(int n){
            parent.resize(n+1);
            sz.resize(n+1,1);
            for(int i=0;i<n+1;i++) parent[i]=i;
        }
        int findPar(int node){
            if(parent[node]==node) return node;
            return parent[node] = findPar(parent[node]);
        }
        void uz(int node1,int node2){
            int p1 = findPar(node1);
            int p2 = findPar(node2);
            if(p1==p2) return;
            if(sz[p1]>sz[p2]){
                parent[p2]=parent[p1];
                sz[p1] += sz[p2];
            }else{
                parent[p1]=parent[p2];
                sz[p2] += sz[p1];
            }
        }
};


int construct_roads(std::vector<int> x, std::vector<int> y) {
    ll n = x.size();
    
    Disjoint ds(n+10);
    map<ll,map<ll,ll>> hash1;
    map<ll,pair<ll,ll>> hash2;
    map<ll,ll> picked;
    vector<pair<int,int>> arr(n);
    int crInd = 0;
    for(int i=0;i<n;i++){
        hash1[x[i]][y[i]]=crInd;
        hash2[crInd] = {x[i],y[i]};
        arr[i].first = x[i];
        arr[i].second = y[i];
        crInd++;
    }
    sort(arr.begin(),arr.end());
    vector<int> u, v, a, b;
    for(int i=0;i<n;i++){
        int crX = arr[i].first;
        int crY = arr[i].second;
        //cout<<crX<<" "<<crY<<endl;
        //cout<<hash1[crX][crY+2]<<endl;
        if(hash1[crX+2][crY]){
            
            if(ds.findPar(i)!=ds.findPar(hash1[crX+2][crY])){
                ds.uz(i,hash1[crX+2][crY]);
                u.push_back(i);
                v.push_back(hash1[crX+2][crY]);
            }
        }
        if(hash1[crX-2][crY]){
            //cout<<"x"<<endl;
            if(ds.findPar(i)!=ds.findPar(hash1[crX-2][crY])){
                ds.uz(i,hash1[crX-2][crY]);
                u.push_back(i);
                v.push_back(hash1[crX-2][crY]);
            }
        }
        if(hash1[crX][crY+2]){
            //cout<<"x"<<endl;
            if(ds.findPar(i)!=ds.findPar(hash1[crX][crY+2])){
                ds.uz(i,hash1[crX][crY+2]);
                u.push_back(i);
                v.push_back(hash1[crX][crY+2]);
            }
        }
        if(hash1[crX][crY-2]){
            //cout<<"x"<<endl;
            if(ds.findPar(i)!=ds.findPar(hash1[crX][crY-2])){
                ds.uz(i,hash1[crX][crY-2]);
                u.push_back(i);
                v.push_back(hash1[crX][crY-2]);
            }
        }
    }
    set<int> p;
    for(int i=0;i<n;i++){
        p.insert(ds.findPar(i));
    }
    //cout<<p.size()<<endl;
    if(p.size()!=1){
        return 0;
    }
    map<ll,map<ll,ll>> oc;
    for(int i=0;i<n-1;i++){
        int crX = x[u[i]];
        int crY = y[u[i]];
        int nxX = x[v[i]];
        int nxY = y[v[i]];
        if(crX == nxX){
            ll bv = (crY + nxY)/2;
            if(oc[crX + 1][bv]){
                a.push_back(crX - 1);
                b.push_back(bv);
                oc[crX - 1][bv] = 1;
            }else{
                a.push_back(crX + 1);
                b.push_back(bv);
                oc[crX + 1][bv] = 1;
            }
        }else{
            ll av = (crX + nxX) / 2;
            if(oc[av][crY + 1]){
                a.push_back(av);
                b.push_back(crY - 1);
                oc[av][crY - 1] = 1;
            }else{
                a.push_back(av);
                b.push_back(crY + 1);
                oc[av][crY + 1] = 1;
            }
        }
    }
    // bool f=1;
    // for(ll i=0;i<n-1;i++){
    //     if((arr[i+1].first - arr[i].first) != 2){
    //         return 0;
    //     }
    //     u.push_back(arr[i+1].second);
    //     v.push_back(arr[i].second);
    //     a.push_back(1);
    //     b.push_back((arr[i+1].first+arr[i].first)/2);
    // }
    
    
    build(u, v, a, b);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 238 ms 39984 KB Pair u[0]=0 @(2, 15660) and v[0]=31503 @(2, 4) 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 238 ms 39984 KB Pair u[0]=0 @(2, 15660) and v[0]=31503 @(2, 4) 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 238 ms 39984 KB Pair u[0]=0 @(2, 15660) and v[0]=31503 @(2, 4) 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 238 ms 39984 KB Pair u[0]=0 @(2, 15660) and v[0]=31503 @(2, 4) 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 238 ms 39984 KB Pair u[0]=0 @(2, 15660) and v[0]=31503 @(2, 4) 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 238 ms 39984 KB Pair u[0]=0 @(2, 15660) and v[0]=31503 @(2, 4) does not form a valid edge (distance != 2)
10 Halted 0 ms 0 KB -