Submission #788549

#	Time	Username	Problem	Language	Result	Execution time	Memory
788549		alexander707070	Fountain Parks (IOI21_parks)	C++17	55 / 100	907 ms	173068 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,benches,br,k,comp[MAXN],ans[MAXN],dsu[MAXN],w[MAXN],sz[MAXN];
bool li[MAXN];
vector<int> v[MAXN],r[MAXN];
stack<int> st;
 
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 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++){
        dsu[i]=i; sz[i]=1;
        x[i]=X[i]; y[i]=Y[i];
        mp[x[i]*300000+y[i]]=i+1;
    }
 
    br=0;
    for(int i=0;i<n;i++){
        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++){
        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;
        }
    }
 
    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++){
        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)])return 0;
        if(comp[i]<comp[op(i)])ans[i]=0;
        else ans[i]=1;
    }
 
    for(int i=0;i<n;i++){
        dsu[i]=i; sz[i]=1;
    }
 
    br=0;
    for(int i=0;i<n;i++){
        curr=mp[(x[i]-2)*300000+y[i]];
        if(curr!=0 and root(i)!=root(curr-1)){
            curr--; mergev(i,curr);
        
            if(ans[br]==0 and ans[br+1]==0)return -1;
            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;
        }
    }
    
    for(int i=0;i<n;i++){
        curr=mp[x[i]*300000+y[i]-2];
        if(curr!=0 and root(i)!=root(curr-1)){
            curr--; mergev(i,curr);
 
            if(ans[br]==0 and ans[br+1]==0)return -1;
            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;
        }
    }
    
    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;
}
 
/*
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:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<bro[x*300000+y].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~
parks.cpp: In function 'void dfs(int)':
parks.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'void scc(int)':
parks.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:105: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]
  105 |     for(int i=0;i<ors.size();i++){
      |                 ~^~~~~~~~~~~
parks.cpp:142:43: 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]
  142 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:142:50: 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]
  142 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:144:43: 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]
  144 |                 sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp:144:50: 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]
  144 |                 sol.push_back({curr,i,x[i]-1,y[i]+1});
parks.cpp:158:43: 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]
  158 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:158:50: 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]
  158 |                 sol.push_back({curr,i,x[i]-1,y[i]-1});
parks.cpp:160:43: 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]
  160 |                 sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:160:50: 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]
  160 |                 sol.push_back({curr,i,x[i]+1,y[i]-1});
parks.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~

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