Submission #788543

#	Time	Username	Problem	Language	Result	Execution time	Memory
788543		alexander707070	Fountain Parks (IOI21_parks)	C++17	5 / 100	695 ms	153348 KiB

parks

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

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

int n,curr,br,k,comp[MAXN],ans[MAXN],dsu[MAXN],w[MAXN],sz[MAXN];
bool li[MAXN];
vector<int> v[MAXN],r[MAXN];
stack<int> st;

bool fail;

vector<bench> sol;
vector<int> A,B,C,D;
vector< pair<int,int> > ors;

unordered_map<long long, int> mp;
unordered_map<long long, vector<int> > bro;

int op(int x){
    if(x<400000)return x+400000;
    return x-400000;
}

void add(long long x,long long y,int z){
    for(int i=0;i<bro[x*300000+y].size();i++){
        ors.push_back({op(bro[x*300000+y][i]),op(z)});
    }
    bro[x*300000+y].push_back(z);
}

void dfs(int x){
    li[x]=true;
    for(int i=0;i<v[x].size();i++){
        if(!li[v[x][i]])dfs(v[x][i]);
    }
    st.push(x);
}

void scc(int x){
    comp[x]=k;
    li[x]=true;

    for(int i=0;i<r[x].size();i++){
        if(!li[r[x][i]])scc(r[x][i]);
    }
}

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

void mergev(int x,int y){
    if(sz[root(x)]<sz[root(y)])swap(x,y);
    sz[root(x)]+=sz[root(y)];
    dsu[root(y)]=root(x);
}

vector<long long> x,y;
int perm[MAXN];

void calc_ors(){
    br=0;
    for(int i=0;i<n;i++){
        if(w[i]==0){
            curr=mp[x[i]*300000+y[i]-2];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);

                add(x[i]-1,y[i]-1,br);
                add(x[i]+1,y[i]-1,br+1);
                ors.push_back({br,br+1});

                br+=2;
            }
        }else{
            curr=mp[(x[i]-2)*300000+y[i]];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);

                add(x[i]-1,y[i]-1,br);
                add(x[i]-1,y[i]+1,br+1);
                ors.push_back({br,br+1});
                
                br+=2;
            }
        }
    }
    for(int i=0;i<n;i++){
        if(w[i]==1){
            curr=mp[x[i]*300000+y[i]-2];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);

                add(x[i]-1,y[i]-1,br);
                add(x[i]+1,y[i]-1,br+1);
                ors.push_back({br,br+1});

                br+=2;
            }
        }else{
            curr=mp[(x[i]-2)*300000+y[i]];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);

                add(x[i]-1,y[i]-1,br);
                add(x[i]-1,y[i]+1,br+1);
                ors.push_back({br,br+1});
                
                br+=2;
            }
        }
    }
}

void find_sol(){
    br=0;
    for(int i=0;i<n;i++){
        if(w[i]==0){
            curr=mp[x[i]*300000+y[i]-2];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);

                if(ans[br]==1){
                    sol.push_back({curr,i,x[i]-1,y[i]-1});
                }else{
                    sol.push_back({curr,i,x[i]+1,y[i]-1});
                }

                br+=2;
            }
        }else{
            curr=mp[(x[i]-2)*300000+y[i]];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);
            
                if(ans[br]==1){
                    sol.push_back({curr,i,x[i]-1,y[i]-1});
                }else{
                    sol.push_back({curr,i,x[i]-1,y[i]+1});
                }
                
                br+=2;
            }
        }
    }

    br=0;
    for(int i=0;i<n;i++){
        if(w[i]==1){
            curr=mp[x[i]*300000+y[i]-2];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);

                if(ans[br]==1){
                    sol.push_back({curr,i,x[i]-1,y[i]-1});
                }else{
                    sol.push_back({curr,i,x[i]+1,y[i]-1});
                }

                br+=2;
            }
        }else{
            curr=mp[(x[i]-2)*300000+y[i]];
            if(curr!=0 and root(i)!=root(curr-1)){
                curr--; mergev(i,curr);
            
                if(ans[br]==1){
                    sol.push_back({curr,i,x[i]-1,y[i]-1});
                }else{
                    sol.push_back({curr,i,x[i]-1,y[i]+1});
                }
                
                br+=2;
            }
        }
    }
}

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

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

    for(int test=0;test<4;test++){
        //random_shuffle(perm,perm+n);
        ors.clear(); fail=false;

        for(int i=0;i<800000;i++){
            v[i].clear(); r[i].clear();
        }
        mp.clear(); bro.clear(); k=0;
        
        for(int i=0;i<n;i++){
            dsu[i]=i; sz[i]=1;
            x[i]=X[perm[i]]; y[i]=Y[perm[i]];
            mp[x[i]*300000+y[i]]=i+1;
        }

        for(int i=0;i<n;i++){
            w[i]=rand()%2;
        }
        calc_ors();

        if(br!=2*n-2)return 0;

        for(int i=0;i<ors.size();i++){
            v[op(ors[i].first)].push_back(ors[i].second);
            r[ors[i].second].push_back(op(ors[i].first));

            v[op(ors[i].second)].push_back(ors[i].first);
            r[ors[i].first].push_back(op(ors[i].second));
        }

        for(int i=0;i<800000;i++)li[i]=false;
        for(int i=0;i<800000;i++){
            if(!li[i])dfs(i);
        }
        for(int i=0;i<800000;i++)li[i]=false;
        while(!st.empty()){
            if(!li[st.top()]){
                k++; scc(st.top());
            }
            st.pop();
        }

        for(int i=0;i<br;i++){
            if(comp[i]==comp[op(i)])fail=true;
            if(comp[i]<comp[op(i)])ans[i]=0;
            else ans[i]=1;
        }

        if(fail)continue;

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

        find_sol();
        
        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);
        return 1;

    }

    return 0;
}

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

Compilation message (stderr)

parks.cpp: In function 'void add(long long int, long long int, int)':
parks.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0;i<bro[x*300000+y].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~
parks.cpp: In function 'void dfs(int)':
parks.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'void scc(int)':
parks.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'void find_sol()':
parks.cpp:132:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  132 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:132:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  132 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:134:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  134 |                     sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:134:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  134 |                     sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:145:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  145 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:145:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  145 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:147:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  147 |                     sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp:147:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  147 |                     sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp:163:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  163 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:163:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  163 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:165:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  165 |                     sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:165:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  165 |                     sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:176:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  176 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:176:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  176 |                     sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:178:47: warning: narrowing conversion of '(x.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) - 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  178 |                     sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp:178:54: warning: narrowing conversion of '(y.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)) + 1)' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
  178 |                     sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:215:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |         for(int i=0;i<ors.size();i++){
      |                     ~^~~~~~~~~~~
parks.cpp:249:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |         for(int i=0;i<sol.size();i++){
      |                     ~^~~~~~~~~~~

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