oj.uz

Submission #788544

# Submission time Handle Problem Language Result Execution time Memory
788544 2023-07-20T10:40:33 Z alexander707070 Fountain Parks (IOI21_parks) C++17
5 / 100
 586 ms 152432 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<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]=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 31 ms 45044 KB Output is correct
2 Correct 30 ms 45012 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 32 ms 45012 KB Output is correct
5 Correct 31 ms 45064 KB Output is correct
6 Correct 21 ms 37916 KB Output is correct
7 Correct 21 ms 37844 KB Output is correct
8 Correct 23 ms 37844 KB Output is correct
9 Correct 200 ms 96392 KB Output is correct
10 Correct 41 ms 49580 KB Output is correct
11 Correct 84 ms 71228 KB Output is correct
12 Correct 56 ms 52124 KB Output is correct
13 Correct 50 ms 53224 KB Output is correct
14 Correct 22 ms 38144 KB Output is correct
15 Correct 22 ms 38456 KB Output is correct
16 Correct 214 ms 96428 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 45044 KB Output is correct
2 Correct 30 ms 45012 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 32 ms 45012 KB Output is correct
5 Correct 31 ms 45064 KB Output is correct
6 Correct 21 ms 37916 KB Output is correct
7 Correct 21 ms 37844 KB Output is correct
8 Correct 23 ms 37844 KB Output is correct
9 Correct 200 ms 96392 KB Output is correct
10 Correct 41 ms 49580 KB Output is correct
11 Correct 84 ms 71228 KB Output is correct
12 Correct 56 ms 52124 KB Output is correct
13 Correct 50 ms 53224 KB Output is correct
14 Correct 22 ms 38144 KB Output is correct
15 Correct 22 ms 38456 KB Output is correct
16 Correct 214 ms 96428 KB Output is correct
17 Incorrect 31 ms 45012 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 31 ms 45044 KB Output is correct
2 Correct 30 ms 45012 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 32 ms 45012 KB Output is correct
5 Correct 31 ms 45064 KB Output is correct
6 Correct 21 ms 37916 KB Output is correct
7 Correct 21 ms 37844 KB Output is correct
8 Correct 23 ms 37844 KB Output is correct
9 Correct 200 ms 96392 KB Output is correct
10 Correct 41 ms 49580 KB Output is correct
11 Correct 84 ms 71228 KB Output is correct
12 Correct 56 ms 52124 KB Output is correct
13 Correct 50 ms 53224 KB Output is correct
14 Correct 22 ms 38144 KB Output is correct
15 Correct 22 ms 38456 KB Output is correct
16 Correct 214 ms 96428 KB Output is correct
17 Incorrect 31 ms 45012 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 31 ms 45044 KB Output is correct
2 Correct 30 ms 45012 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 32 ms 45012 KB Output is correct
5 Correct 31 ms 45064 KB Output is correct
6 Correct 21 ms 37916 KB Output is correct
7 Correct 21 ms 37844 KB Output is correct
8 Correct 23 ms 37844 KB Output is correct
9 Correct 200 ms 96392 KB Output is correct
10 Correct 41 ms 49580 KB Output is correct
11 Correct 84 ms 71228 KB Output is correct
12 Correct 56 ms 52124 KB Output is correct
13 Correct 50 ms 53224 KB Output is correct
14 Correct 22 ms 38144 KB Output is correct
15 Correct 22 ms 38456 KB Output is correct
16 Correct 214 ms 96428 KB Output is correct
17 Correct 31 ms 45004 KB Output is correct
18 Incorrect 29 ms 45012 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 31 ms 45044 KB Output is correct
2 Correct 30 ms 45012 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 32 ms 45012 KB Output is correct
5 Correct 31 ms 45064 KB Output is correct
6 Correct 21 ms 37916 KB Output is correct
7 Correct 21 ms 37844 KB Output is correct
8 Correct 23 ms 37844 KB Output is correct
9 Correct 200 ms 96392 KB Output is correct
10 Correct 41 ms 49580 KB Output is correct
11 Correct 84 ms 71228 KB Output is correct
12 Correct 56 ms 52124 KB Output is correct
13 Correct 50 ms 53224 KB Output is correct
14 Correct 22 ms 38144 KB Output is correct
15 Correct 22 ms 38456 KB Output is correct
16 Correct 214 ms 96428 KB Output is correct
17 Incorrect 586 ms 152432 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 31 ms 45044 KB Output is correct
2 Correct 30 ms 45012 KB Output is correct
3 Correct 21 ms 37876 KB Output is correct
4 Correct 32 ms 45012 KB Output is correct
5 Correct 31 ms 45064 KB Output is correct
6 Correct 21 ms 37916 KB Output is correct
7 Correct 21 ms 37844 KB Output is correct
8 Correct 23 ms 37844 KB Output is correct
9 Correct 200 ms 96392 KB Output is correct
10 Correct 41 ms 49580 KB Output is correct
11 Correct 84 ms 71228 KB Output is correct
12 Correct 56 ms 52124 KB Output is correct
13 Correct 50 ms 53224 KB Output is correct
14 Correct 22 ms 38144 KB Output is correct
15 Correct 22 ms 38456 KB Output is correct
16 Correct 214 ms 96428 KB Output is correct
17 Incorrect 31 ms 45012 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -