Submission #788427

#	Time	Username	Problem	Language	Result	Execution time	Memory
788427		alexander707070	Fountain Parks (IOI21_parks)	C++17	0 / 100	0 ms	212 KiB

parks

#include<bits/stdc++.h>
#include "parks.h"
#define MAXN 200007
using namespace std;

struct bench{
    int from,to;
    int a,b;
};

int n,dsu[MAXN],up[MAXN],down[MAXN],curr;
vector< pair<int,int> > l,m,r;
vector<bench> sol;
vector<int> A,B,C,D;

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    dsu[root(x)]=root(y);
}

int construct_roads(vector<int> x,vector<int> y){
    n=int(x.size());

    for(int i=0;i<n;i++){
        dsu[i]=i;

        if(x[i]==2){
            l.push_back({y[i],i});
            down[y[i]]=i+1;
        }
        if(x[i]==4)m.push_back({y[i],i});
        if(x[i]==6){
            r.push_back({y[i],i});
            up[y[i]]=i+1;
        }
    }

    sort(l.begin(),l.end());
    sort(m.begin(),m.end());
    sort(r.begin(),r.end());

    for(int i=0;i<l.size()-1;i++){
        if(l[i].first+2==l[i+1].first){
            mergev(l[i].second,l[i+1].second);
            sol.push_back({l[i].second,l[i+1].second,1,l[i].first+1});
        }
    }

    return 0;

    for(int i=0;i<r.size()-1;i++){
        if(r[i].first+2==r[i+1].first){
            mergev(r[i].second,r[i+1].second);
            sol.push_back({r[i].second,r[i+1].second,7,r[i].first+1});
        }
    }

    for(int i=0;i<m.size()-1;i++){
        if(m[i].first+2==m[i+1].first){
            mergev(m[i].second,m[i+1].second);
            if(m[i].first%4==0)sol.push_back({m[i].second,m[i+1].second,3,m[i].first+1});
            if(m[i].first%4==2)sol.push_back({m[i].second,m[i+1].second,5,m[i].first+1});
        }
    }

    for(int i=0;i<m.size();i++){
        if(down[m[i].first]!=0){
            curr=down[m[i].first]-1;
            if(root(curr)==root(m[i].second))continue;

            mergev(curr,m[i].second);
            if(m[i].first%4==0)sol.push_back({curr,m[i].second,3,m[i].first-1});
            if(m[i].first%4==2)sol.push_back({curr,m[i].second,3,m[i].first+1});
        }
    }

    for(int i=0;i<m.size();i++){
        if(up[m[i].first]!=0){
            curr=up[m[i].first]-1;
            if(root(curr)==root(m[i].second))continue;

            mergev(curr,m[i].second);
            if(m[i].first%4==0)sol.push_back({m[i].second,curr,5,m[i].first+1});
            if(m[i].first%4==2)sol.push_back({m[i].second,curr,5,m[i].first-1});
        }
    }

    for(int i=0;i<n;i++){
        if(root(i)!=root(0))return 0;
    }

    for(int i=0;i<sol.size();i++){
        A.push_back(sol[i].from);
        B.push_back(sol[i].to);
        C.push_back(sol[i].a);
        D.push_back(sol[i].b);
    }

    build(A,B,C,D);
}

/*
int main(){
    construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
*/

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<l.size()-1;i++){
      |                 ~^~~~~~~~~~~
parks.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<r.size()-1;i++){
      |                 ~^~~~~~~~~~~
parks.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<m.size()-1;i++){
      |                 ~^~~~~~~~~~~
parks.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<m.size();i++){
      |                 ~^~~~~~~~~
parks.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i=0;i<m.size();i++){
      |                 ~^~~~~~~~~
parks.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30