oj.uz

Submission #836805

# Submission time Handle Problem Language Result Execution time Memory
836805 2023-08-24T16:00:23 Z ma_moutahid Fountain Parks (IOI21_parks) C++17
5 / 100
 118 ms 42764 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define vii vector<vi>
#define pi pair<int,int>
#define vp vector<pi>

vi d;
vi h;
int parent(int x){
    if(d[x]==x)return x;
    return d[x]=parent(d[x]);
}
void connect(int a, int b){
    a=parent(a);
    b=parent(b);
    if(h[a]<h[b])swap(a,b);
    if(h[a]==h[b])h[a]++;
    d[b]=a;
}



int construct_roads(std::vector<int> x, std::vector<int> y) {
    //bsmllah
    int n=x.size();
    d.resize(n);for(int i=0;i<n;i++)d[i]=i;
    h.resize(n);
    vi u;
    vi v;
    vi a;
    vi b;

    map<pi,int>f;
    for(int i=0;i<n;i++){
        f.insert(make_pair(pi(x[i],y[i]),i));
    }
    vii k(4, vi(200001,-1));
    for(int i=0;i<n;i++){
        k[x[i]/2][y[i]]=i;
        if(x[i]==4){
            continue;
        }
    
        auto itr=f.find(pi(x[i]+2,y[i]));
        if(itr!=f.end()){
            u.push_back(i);
            v.push_back(itr->second);
            a.push_back(x[i]+1);
            b.push_back(y[i]+1);
            connect(i,itr->second);
        }
        itr=f.find(pi(x[i],y[i]+2));
        if(itr!=f.end()){
            u.push_back(i);
            v.push_back(itr->second);
            a.push_back(x[i]+x[i]-3);
            b.push_back(y[i]+1);
            connect(i,itr->second);
        }
    }
    if(k[2][2]!=-1){
        if(k[1][2]!=-1){
            u.push_back(k[1][2]);
            v.push_back(k[2][2]);
            connect(k[1][2],k[2][2]);
            a.push_back(3);
            b.push_back(1);
        }
        if(k[3][2]!=-1){
            u.push_back(k[3][2]);
            v.push_back(k[2][2]);
            connect(k[3][2],k[2][2]);
            a.push_back(5);
            b.push_back(1);
        }
    }
    for(int i=4;i<200001;i+=2){
        if(k[2][i]==-1)continue;
        if(k[2][i-2]==-1){
            if(k[1][i]!=-1){
                u.push_back(k[1][i]);
                v.push_back(k[2][i]);
                a.push_back(3);
                b.push_back(i-1);
            }
            if(k[3][i]!=-1){
                u.push_back(k[3][i]);
                v.push_back(k[2][i]);
                a.push_back(5);
                b.push_back(i-1);
            }
            continue;
        }
        u.push_back(k[2][i]);
        v.push_back(k[2][i-2]);
        b.push_back(i-1);
        if(i%4){
            a.push_back(5);
        }
        else{
            a.push_back(3);
        }
        connect(k[2][i],k[2][i-2]);
        if(k[3][i-2]==1 && k[3][i]!=-1){
            u.push_back(k[3][i]);
            v.push_back(k[2][i]);
            a.push_back(5);
            if(i%4){
                b.push_back(i+1);
            }
            else {
                b.push_back(i-1);
            }
            connect(k[3][i],k[2][i]);
        }
        if(k[1][i-2]==1 && k[1][i]!=-1){
            u.push_back(k[1][i]);
            v.push_back(k[2][i]);
            a.push_back(3);
            if(i%4){
                b.push_back(i-1);
            }
            else {
                b.push_back(i+1);
            }
            connect(k[1][i],k[2][i]);
        }
        
    }


    for(int i=0;i<n;i++){
        if(parent(d[i])!=parent(d[0]))return 0;
    }

    build(u,v,a,b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4136 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4136 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4140 KB Output is correct
8 Correct 2 ms 4136 KB Output is correct
9 Correct 118 ms 17824 KB Output is correct
10 Correct 8 ms 5048 KB Output is correct
11 Correct 40 ms 11152 KB Output is correct
12 Correct 12 ms 5560 KB Output is correct
13 Correct 22 ms 8896 KB Output is correct
14 Correct 2 ms 4308 KB Output is correct
15 Correct 3 ms 4404 KB Output is correct
16 Correct 107 ms 17820 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4136 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4136 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4140 KB Output is correct
8 Correct 2 ms 4136 KB Output is correct
9 Correct 118 ms 17824 KB Output is correct
10 Correct 8 ms 5048 KB Output is correct
11 Correct 40 ms 11152 KB Output is correct
12 Correct 12 ms 5560 KB Output is correct
13 Correct 22 ms 8896 KB Output is correct
14 Correct 2 ms 4308 KB Output is correct
15 Correct 3 ms 4404 KB Output is correct
16 Correct 107 ms 17820 KB Output is correct
17 Incorrect 2 ms 4180 KB Edge between 3 and 2 appears more than once: appeared on positions 1 and 3
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4136 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4136 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4140 KB Output is correct
8 Correct 2 ms 4136 KB Output is correct
9 Correct 118 ms 17824 KB Output is correct
10 Correct 8 ms 5048 KB Output is correct
11 Correct 40 ms 11152 KB Output is correct
12 Correct 12 ms 5560 KB Output is correct
13 Correct 22 ms 8896 KB Output is correct
14 Correct 2 ms 4308 KB Output is correct
15 Correct 3 ms 4404 KB Output is correct
16 Correct 107 ms 17820 KB Output is correct
17 Incorrect 2 ms 4180 KB Edge between 3 and 2 appears more than once: appeared on positions 1 and 3
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4136 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4136 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4140 KB Output is correct
8 Correct 2 ms 4136 KB Output is correct
9 Correct 118 ms 17824 KB Output is correct
10 Correct 8 ms 5048 KB Output is correct
11 Correct 40 ms 11152 KB Output is correct
12 Correct 12 ms 5560 KB Output is correct
13 Correct 22 ms 8896 KB Output is correct
14 Correct 2 ms 4308 KB Output is correct
15 Correct 3 ms 4404 KB Output is correct
16 Correct 107 ms 17820 KB Output is correct
17 Runtime error 4 ms 6684 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4136 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4136 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4140 KB Output is correct
8 Correct 2 ms 4136 KB Output is correct
9 Correct 118 ms 17824 KB Output is correct
10 Correct 8 ms 5048 KB Output is correct
11 Correct 40 ms 11152 KB Output is correct
12 Correct 12 ms 5560 KB Output is correct
13 Correct 22 ms 8896 KB Output is correct
14 Correct 2 ms 4308 KB Output is correct
15 Correct 3 ms 4404 KB Output is correct
16 Correct 107 ms 17820 KB Output is correct
17 Runtime error 110 ms 42764 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4136 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4136 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4140 KB Output is correct
8 Correct 2 ms 4136 KB Output is correct
9 Correct 118 ms 17824 KB Output is correct
10 Correct 8 ms 5048 KB Output is correct
11 Correct 40 ms 11152 KB Output is correct
12 Correct 12 ms 5560 KB Output is correct
13 Correct 22 ms 8896 KB Output is correct
14 Correct 2 ms 4308 KB Output is correct
15 Correct 3 ms 4404 KB Output is correct
16 Correct 107 ms 17820 KB Output is correct
17 Incorrect 2 ms 4180 KB Edge between 3 and 2 appears more than once: appeared on positions 1 and 3
18 Halted 0 ms 0 KB -