oj.uz

Submission #1049874

# Submission time Handle Problem Language Result Execution time Memory
1049874 2024-08-09T05:51:47 Z nisanduu Fountain Parks (IOI21_parks) C++17
5 / 100
 629 ms 90120 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 = 1;
    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]-1)){
                ds.uz(i,hash1[crX+2][crY]-1);
                u.push_back(i);
                v.push_back(hash1[crX+2][crY]-1);
            }
        }
        if(hash1[crX-2][crY]){
            //cout<<"x"<<endl;
            if(ds.findPar(i)!=ds.findPar(hash1[crX-2][crY]-1)){
                ds.uz(i,hash1[crX-2][crY]-1);
                u.push_back(i);
                v.push_back(hash1[crX-2][crY]-1);
            }
        }
        if(hash1[crX][crY+2]){
            //cout<<"x"<<endl;
            if(ds.findPar(i)!=ds.findPar(hash1[crX][crY+2]-1)){
                ds.uz(i,hash1[crX][crY+2]-1);
                u.push_back(i);
                v.push_back(hash1[crX][crY+2]-1);
            }
        }
        if(hash1[crX][crY-2]){
            //cout<<"x"<<endl;
            if(ds.findPar(i)!=ds.findPar(hash1[crX][crY-2]-1)){
                ds.uz(i,hash1[crX][crY-2]-1);
                u.push_back(i);
                v.push_back(hash1[crX][crY-2]-1);
            }
        }
    }
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 249 ms 39444 KB Output is correct
10 Correct 11 ms 4540 KB Output is correct
11 Correct 77 ms 21836 KB Output is correct
12 Correct 23 ms 6492 KB Output is correct
13 Correct 55 ms 13384 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 247 ms 40208 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 249 ms 39444 KB Output is correct
10 Correct 11 ms 4540 KB Output is correct
11 Correct 77 ms 21836 KB Output is correct
12 Correct 23 ms 6492 KB Output is correct
13 Correct 55 ms 13384 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 247 ms 40208 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 6
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 249 ms 39444 KB Output is correct
10 Correct 11 ms 4540 KB Output is correct
11 Correct 77 ms 21836 KB Output is correct
12 Correct 23 ms 6492 KB Output is correct
13 Correct 55 ms 13384 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 247 ms 40208 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 6
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 249 ms 39444 KB Output is correct
10 Correct 11 ms 4540 KB Output is correct
11 Correct 77 ms 21836 KB Output is correct
12 Correct 23 ms 6492 KB Output is correct
13 Correct 55 ms 13384 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 247 ms 40208 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 356 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 582 ms 85768 KB Tree @(175837, 24165) appears more than once: for edges on positions 5504 and 5505
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 249 ms 39444 KB Output is correct
10 Correct 11 ms 4540 KB Output is correct
11 Correct 77 ms 21836 KB Output is correct
12 Correct 23 ms 6492 KB Output is correct
13 Correct 55 ms 13384 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 247 ms 40208 KB Output is correct
17 Correct 622 ms 90120 KB Output is correct
18 Correct 629 ms 90076 KB Output is correct
19 Incorrect 563 ms 76856 KB Tree @(43595, 6409) appears more than once: for edges on positions 7880 and 7881
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 249 ms 39444 KB Output is correct
10 Correct 11 ms 4540 KB Output is correct
11 Correct 77 ms 21836 KB Output is correct
12 Correct 23 ms 6492 KB Output is correct
13 Correct 55 ms 13384 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 247 ms 40208 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 6
21 Halted 0 ms 0 KB -