oj.uz

Submission #788546

# Submission time Handle Problem Language Result Execution time Memory
788546 2023-07-20T10:40:58 Z alexander707070 Fountain Parks (IOI21_parks) C++17
5 / 100
 674 ms 152492 KB 
#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<1;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]=0;
        }
        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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45012 KB Output is correct
2 Correct 32 ms 45072 KB Output is correct
3 Correct 25 ms 37884 KB Output is correct
4 Correct 29 ms 45004 KB Output is correct
5 Correct 29 ms 45088 KB Output is correct
6 Correct 19 ms 37892 KB Output is correct
7 Correct 26 ms 37876 KB Output is correct
8 Correct 25 ms 37852 KB Output is correct
9 Correct 211 ms 96424 KB Output is correct
10 Correct 38 ms 49600 KB Output is correct
11 Correct 81 ms 71240 KB Output is correct
12 Correct 48 ms 52084 KB Output is correct
13 Correct 42 ms 53320 KB Output is correct
14 Correct 21 ms 38224 KB Output is correct
15 Correct 23 ms 38436 KB Output is correct
16 Correct 200 ms 96488 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45012 KB Output is correct
2 Correct 32 ms 45072 KB Output is correct
3 Correct 25 ms 37884 KB Output is correct
4 Correct 29 ms 45004 KB Output is correct
5 Correct 29 ms 45088 KB Output is correct
6 Correct 19 ms 37892 KB Output is correct
7 Correct 26 ms 37876 KB Output is correct
8 Correct 25 ms 37852 KB Output is correct
9 Correct 211 ms 96424 KB Output is correct
10 Correct 38 ms 49600 KB Output is correct
11 Correct 81 ms 71240 KB Output is correct
12 Correct 48 ms 52084 KB Output is correct
13 Correct 42 ms 53320 KB Output is correct
14 Correct 21 ms 38224 KB Output is correct
15 Correct 23 ms 38436 KB Output is correct
16 Correct 200 ms 96488 KB Output is correct
17 Incorrect 29 ms 45064 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45012 KB Output is correct
2 Correct 32 ms 45072 KB Output is correct
3 Correct 25 ms 37884 KB Output is correct
4 Correct 29 ms 45004 KB Output is correct
5 Correct 29 ms 45088 KB Output is correct
6 Correct 19 ms 37892 KB Output is correct
7 Correct 26 ms 37876 KB Output is correct
8 Correct 25 ms 37852 KB Output is correct
9 Correct 211 ms 96424 KB Output is correct
10 Correct 38 ms 49600 KB Output is correct
11 Correct 81 ms 71240 KB Output is correct
12 Correct 48 ms 52084 KB Output is correct
13 Correct 42 ms 53320 KB Output is correct
14 Correct 21 ms 38224 KB Output is correct
15 Correct 23 ms 38436 KB Output is correct
16 Correct 200 ms 96488 KB Output is correct
17 Incorrect 29 ms 45064 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45012 KB Output is correct
2 Correct 32 ms 45072 KB Output is correct
3 Correct 25 ms 37884 KB Output is correct
4 Correct 29 ms 45004 KB Output is correct
5 Correct 29 ms 45088 KB Output is correct
6 Correct 19 ms 37892 KB Output is correct
7 Correct 26 ms 37876 KB Output is correct
8 Correct 25 ms 37852 KB Output is correct
9 Correct 211 ms 96424 KB Output is correct
10 Correct 38 ms 49600 KB Output is correct
11 Correct 81 ms 71240 KB Output is correct
12 Correct 48 ms 52084 KB Output is correct
13 Correct 42 ms 53320 KB Output is correct
14 Correct 21 ms 38224 KB Output is correct
15 Correct 23 ms 38436 KB Output is correct
16 Correct 200 ms 96488 KB Output is correct
17 Correct 27 ms 45044 KB Output is correct
18 Incorrect 27 ms 45000 KB Tree @(199999, 199999) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45012 KB Output is correct
2 Correct 32 ms 45072 KB Output is correct
3 Correct 25 ms 37884 KB Output is correct
4 Correct 29 ms 45004 KB Output is correct
5 Correct 29 ms 45088 KB Output is correct
6 Correct 19 ms 37892 KB Output is correct
7 Correct 26 ms 37876 KB Output is correct
8 Correct 25 ms 37852 KB Output is correct
9 Correct 211 ms 96424 KB Output is correct
10 Correct 38 ms 49600 KB Output is correct
11 Correct 81 ms 71240 KB Output is correct
12 Correct 48 ms 52084 KB Output is correct
13 Correct 42 ms 53320 KB Output is correct
14 Correct 21 ms 38224 KB Output is correct
15 Correct 23 ms 38436 KB Output is correct
16 Correct 200 ms 96488 KB Output is correct
17 Incorrect 674 ms 152492 KB Tree @(100001, 100001) appears more than once: for edges on positions 40711 and 140913
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 45012 KB Output is correct
2 Correct 32 ms 45072 KB Output is correct
3 Correct 25 ms 37884 KB Output is correct
4 Correct 29 ms 45004 KB Output is correct
5 Correct 29 ms 45088 KB Output is correct
6 Correct 19 ms 37892 KB Output is correct
7 Correct 26 ms 37876 KB Output is correct
8 Correct 25 ms 37852 KB Output is correct
9 Correct 211 ms 96424 KB Output is correct
10 Correct 38 ms 49600 KB Output is correct
11 Correct 81 ms 71240 KB Output is correct
12 Correct 48 ms 52084 KB Output is correct
13 Correct 42 ms 53320 KB Output is correct
14 Correct 21 ms 38224 KB Output is correct
15 Correct 23 ms 38436 KB Output is correct
16 Correct 200 ms 96488 KB Output is correct
17 Incorrect 29 ms 45064 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -