oj.uz

Submission #688324

# Submission time Handle Problem Language Result Execution time Memory
688324 2023-01-27T10:06:18 Z coding_snorlax Fountain Parks (IOI21_parks) C++17
5 / 100
 173 ms 34168 KB 
#include<bits/stdc++.h>
#include "parks.h"
using namespace std;
#define mp make_pair
#define pb push_back
vector<pair<int,int>> G;
vector<pair<int,int>> x_axis[200005];
vector<pair<int,int>> y_axis[200005];
vector<pair<int,int>> choose;
vector<int> u,v,a,b;
int Boss[200005];
int query(int node){
    if(Boss[node]==node) return node;
    return Boss[node]=query(Boss[node]);
}
int Union(int x,int y){
    if(query(x)==query(y)) return 0;
    Boss[query(x)]=query(y);
    return 1;
}
int construct_roads(vector<int> x,vector<int> y){
    for(int i=0;i<200005;i++){
        Boss[i]=i;
    }
    for(int i=0;i<(int)x.size();i++){
        x_axis[x[i]].pb(mp(y[i],i));
        y_axis[y[i]].pb(mp(x[i],i));
    }
    for(int i=0;i<200005;i++){
        sort(x_axis[i].begin(),x_axis[i].end());
        sort(y_axis[i].begin(),y_axis[i].end());
    }
    //construct graph
    for(int i=0;i<200005;i++){
        for(int j=0;j<(int)x_axis[i].size()-1;j++){
            //cout<<x_axis[i][j+1].first<<"\n";
            if(x_axis[i][j+1].first-x_axis[i][j].first==2){
                G.pb(mp(x_axis[i][j+1].second,x_axis[i][j].second));
            }
        }
        for(int j=0;j<(int)y_axis[i].size()-1;j++){
            if(y_axis[i][j+1].first-y_axis[i][j].first==2){
                G.pb(mp(y_axis[i][j+1].second,y_axis[i][j].second));
            }
        }
    }
    for(auto i:G){
        //cout<<i.first<<" "<<i.second<<"\n";
        if(Union(i.first,i.second)){
            choose.pb(mp(i.first,i.second));
        }
    }
    for(auto i:choose){
        //cout<<x[i.first]<<" "<<y[i.first]<<" "<<x[i.second]<<" "<<y[i.second]<<"\n";
        if(x[i.first]==x[i.second] && x[i.first]==2){
            u.pb(i.first);v.pb(i.second);a.pb(1);b.pb((y[i.first]+y[i.second])/2);
        }
        else if(x[i.first]==x[i.second] && x[i.first]==4){
            u.pb(i.first);v.pb(i.second);a.pb(5);b.pb((y[i.first]+y[i.second])/2);
        }
        else{
            u.pb(i.first);v.pb(i.second);a.pb(x[i.first]+1);b.pb(3);
        }
        //cout<<v.back()<<" \n";
    }
    //for(int i:v) cout<<i<<" ";
    if((int)choose.size()==(int)x.size()-1){
        build(u,v,a,b);
        return 1;
    }
    return 0;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 75 ms 23756 KB Output is correct
10 Correct 12 ms 11860 KB Output is correct
11 Correct 36 ms 17552 KB Output is correct
12 Correct 14 ms 12512 KB Output is correct
13 Correct 17 ms 14804 KB Output is correct
14 Correct 8 ms 10488 KB Output is correct
15 Correct 7 ms 10580 KB Output is correct
16 Correct 75 ms 23756 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 75 ms 23756 KB Output is correct
10 Correct 12 ms 11860 KB Output is correct
11 Correct 36 ms 17552 KB Output is correct
12 Correct 14 ms 12512 KB Output is correct
13 Correct 17 ms 14804 KB Output is correct
14 Correct 8 ms 10488 KB Output is correct
15 Correct 7 ms 10580 KB Output is correct
16 Correct 75 ms 23756 KB Output is correct
17 Incorrect 6 ms 10392 KB Tree (a[1], b[1]) = (5, 3) is not adjacent to edge between u[1]=2 @(4, 2) and v[1]=3 @(2, 2)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 75 ms 23756 KB Output is correct
10 Correct 12 ms 11860 KB Output is correct
11 Correct 36 ms 17552 KB Output is correct
12 Correct 14 ms 12512 KB Output is correct
13 Correct 17 ms 14804 KB Output is correct
14 Correct 8 ms 10488 KB Output is correct
15 Correct 7 ms 10580 KB Output is correct
16 Correct 75 ms 23756 KB Output is correct
17 Incorrect 6 ms 10392 KB Tree (a[1], b[1]) = (5, 3) is not adjacent to edge between u[1]=2 @(4, 2) and v[1]=3 @(2, 2)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 75 ms 23756 KB Output is correct
10 Correct 12 ms 11860 KB Output is correct
11 Correct 36 ms 17552 KB Output is correct
12 Correct 14 ms 12512 KB Output is correct
13 Correct 17 ms 14804 KB Output is correct
14 Correct 8 ms 10488 KB Output is correct
15 Correct 7 ms 10580 KB Output is correct
16 Correct 75 ms 23756 KB Output is correct
17 Incorrect 6 ms 10452 KB Tree (a[0], b[0]) = (200001, 3) is not adjacent to edge between u[0]=0 @(200000, 2) and v[0]=2 @(199998, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 75 ms 23756 KB Output is correct
10 Correct 12 ms 11860 KB Output is correct
11 Correct 36 ms 17552 KB Output is correct
12 Correct 14 ms 12512 KB Output is correct
13 Correct 17 ms 14804 KB Output is correct
14 Correct 8 ms 10488 KB Output is correct
15 Correct 7 ms 10580 KB Output is correct
16 Correct 75 ms 23756 KB Output is correct
17 Incorrect 173 ms 34168 KB Tree (a[50000], b[50000]) = (5, 3) is not adjacent to edge between u[50000]=22196 @(4, 2) and v[50000]=199575 @(2, 2)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 7 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 6 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 75 ms 23756 KB Output is correct
10 Correct 12 ms 11860 KB Output is correct
11 Correct 36 ms 17552 KB Output is correct
12 Correct 14 ms 12512 KB Output is correct
13 Correct 17 ms 14804 KB Output is correct
14 Correct 8 ms 10488 KB Output is correct
15 Correct 7 ms 10580 KB Output is correct
16 Correct 75 ms 23756 KB Output is correct
17 Incorrect 6 ms 10392 KB Tree (a[1], b[1]) = (5, 3) is not adjacent to edge between u[1]=2 @(4, 2) and v[1]=3 @(2, 2)
18 Halted 0 ms 0 KB -