Submission #788571

#	Time	Username	Problem	Language	Result	Execution time	Memory
788571		alexander707070	Fountain Parks (IOI21_parks)	C++17	70 / 100	640 ms	178740 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;

void dfss(long long x,long long y){
    int ss=mp[x*300000+y]-1; 
    curr=mp[x*300000+y-2];
    if(curr!=0 and root(ss)!=root(curr-1)){
        curr--; mergev(ss,curr);

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

        br+=2;
        dfss(x,y-2);
    }

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

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

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

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

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

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


void dfss2(long long x,long long y){
    int ss=mp[x*300000+y]-1; 
    curr=mp[x*300000+y-2];
    if(curr!=0 and root(ss)!=root(curr-1)){
        curr--; mergev(ss,curr);

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

        br+=2;
        dfss2(x,y-2);
    }

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

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

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

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

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

        if(ans[br]==1){
            sol.push_back({curr,ss,x+1,y-1});
        }else{
            sol.push_back({curr,ss,x+1,y+1});
        }
        
        br+=2;
        dfss2(x+2,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;
    int start=rand()%n;
    dfss(x[start],y[start]);
 
    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;
    dfss2(x[start],y[start]);
    
    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({2,2,2,2,4,4,4,4,6,6,6,6,8,8,8,8}, {2,4,6,8,2,4,6,8,2,4,6,8,2,4,6,8});
}
*/

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 'void dfss2(long long int, long long int)':
parks.cpp:125:37: warning: narrowing conversion of '(x - 1)' from 'long long int' to 'int' [-Wnarrowing]
  125 |             sol.push_back({curr,ss,x-1,y-1});
      |                                    ~^~
parks.cpp:125:41: warning: narrowing conversion of '(y - 1)' from 'long long int' to 'int' [-Wnarrowing]
  125 |             sol.push_back({curr,ss,x-1,y-1});
      |                                        ~^~
parks.cpp:127:37: warning: narrowing conversion of '(x + 1)' from 'long long int' to 'int' [-Wnarrowing]
  127 |             sol.push_back({curr,ss,x+1,y-1});
      |                                    ~^~
parks.cpp:127:41: warning: narrowing conversion of '(y - 1)' from 'long long int' to 'int' [-Wnarrowing]
  127 |             sol.push_back({curr,ss,x+1,y-1});
      |                                        ~^~
parks.cpp:139:37: warning: narrowing conversion of '(x - 1)' from 'long long int' to 'int' [-Wnarrowing]
  139 |             sol.push_back({curr,ss,x-1,y+1});
      |                                    ~^~
parks.cpp:139:41: warning: narrowing conversion of '(y + 1)' from 'long long int' to 'int' [-Wnarrowing]
  139 |             sol.push_back({curr,ss,x-1,y+1});
      |                                        ~^~
parks.cpp:141:37: warning: narrowing conversion of '(x + 1)' from 'long long int' to 'int' [-Wnarrowing]
  141 |             sol.push_back({curr,ss,x+1,y+1});
      |                                    ~^~
parks.cpp:141:41: warning: narrowing conversion of '(y + 1)' from 'long long int' to 'int' [-Wnarrowing]
  141 |             sol.push_back({curr,ss,x+1,y+1});
      |                                        ~^~
parks.cpp:153:37: warning: narrowing conversion of '(x - 1)' from 'long long int' to 'int' [-Wnarrowing]
  153 |             sol.push_back({curr,ss,x-1,y-1});
      |                                    ~^~
parks.cpp:153:41: warning: narrowing conversion of '(y - 1)' from 'long long int' to 'int' [-Wnarrowing]
  153 |             sol.push_back({curr,ss,x-1,y-1});
      |                                        ~^~
parks.cpp:155:37: warning: narrowing conversion of '(x - 1)' from 'long long int' to 'int' [-Wnarrowing]
  155 |             sol.push_back({curr,ss,x-1,y+1});
      |                                    ~^~
parks.cpp:155:41: warning: narrowing conversion of '(y + 1)' from 'long long int' to 'int' [-Wnarrowing]
  155 |             sol.push_back({curr,ss,x-1,y+1});
      |                                        ~^~
parks.cpp:167:37: warning: narrowing conversion of '(x + 1)' from 'long long int' to 'int' [-Wnarrowing]
  167 |             sol.push_back({curr,ss,x+1,y-1});
      |                                    ~^~
parks.cpp:167:41: warning: narrowing conversion of '(y - 1)' from 'long long int' to 'int' [-Wnarrowing]
  167 |             sol.push_back({curr,ss,x+1,y-1});
      |                                        ~^~
parks.cpp:169:37: warning: narrowing conversion of '(x + 1)' from 'long long int' to 'int' [-Wnarrowing]
  169 |             sol.push_back({curr,ss,x+1,y+1});
      |                                    ~^~
parks.cpp:169:41: warning: narrowing conversion of '(y + 1)' from 'long long int' to 'int' [-Wnarrowing]
  169 |             sol.push_back({curr,ss,x+1,y+1});
      |                                        ~^~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:193: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]
  193 |     for(int i=0;i<ors.size();i++){
      |                 ~^~~~~~~~~~~
parks.cpp:225:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~

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