oj.uz

Submission #788543

# Submission time Handle Problem Language Result Execution time Memory
788543 2023-07-20T10:39:41 Z alexander707070 Fountain Parks (IOI21_parks) C++17
5 / 100
 695 ms 153348 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]=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

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 35 ms 45080 KB Output is correct
2 Correct 37 ms 45036 KB Output is correct
3 Correct 24 ms 37876 KB Output is correct
4 Correct 39 ms 45088 KB Output is correct
5 Correct 34 ms 45004 KB Output is correct
6 Correct 24 ms 37844 KB Output is correct
7 Correct 28 ms 37880 KB Output is correct
8 Correct 23 ms 37888 KB Output is correct
9 Correct 275 ms 97208 KB Output is correct
10 Correct 52 ms 49724 KB Output is correct
11 Correct 93 ms 71684 KB Output is correct
12 Correct 45 ms 52200 KB Output is correct
13 Correct 54 ms 53412 KB Output is correct
14 Correct 21 ms 38228 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct
16 Correct 291 ms 97252 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 45080 KB Output is correct
2 Correct 37 ms 45036 KB Output is correct
3 Correct 24 ms 37876 KB Output is correct
4 Correct 39 ms 45088 KB Output is correct
5 Correct 34 ms 45004 KB Output is correct
6 Correct 24 ms 37844 KB Output is correct
7 Correct 28 ms 37880 KB Output is correct
8 Correct 23 ms 37888 KB Output is correct
9 Correct 275 ms 97208 KB Output is correct
10 Correct 52 ms 49724 KB Output is correct
11 Correct 93 ms 71684 KB Output is correct
12 Correct 45 ms 52200 KB Output is correct
13 Correct 54 ms 53412 KB Output is correct
14 Correct 21 ms 38228 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct
16 Correct 291 ms 97252 KB Output is correct
17 Correct 41 ms 45012 KB Output is correct
18 Correct 33 ms 45088 KB Output is correct
19 Incorrect 33 ms 45096 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 4
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 45080 KB Output is correct
2 Correct 37 ms 45036 KB Output is correct
3 Correct 24 ms 37876 KB Output is correct
4 Correct 39 ms 45088 KB Output is correct
5 Correct 34 ms 45004 KB Output is correct
6 Correct 24 ms 37844 KB Output is correct
7 Correct 28 ms 37880 KB Output is correct
8 Correct 23 ms 37888 KB Output is correct
9 Correct 275 ms 97208 KB Output is correct
10 Correct 52 ms 49724 KB Output is correct
11 Correct 93 ms 71684 KB Output is correct
12 Correct 45 ms 52200 KB Output is correct
13 Correct 54 ms 53412 KB Output is correct
14 Correct 21 ms 38228 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct
16 Correct 291 ms 97252 KB Output is correct
17 Correct 41 ms 45012 KB Output is correct
18 Correct 33 ms 45088 KB Output is correct
19 Incorrect 33 ms 45096 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 4
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 45080 KB Output is correct
2 Correct 37 ms 45036 KB Output is correct
3 Correct 24 ms 37876 KB Output is correct
4 Correct 39 ms 45088 KB Output is correct
5 Correct 34 ms 45004 KB Output is correct
6 Correct 24 ms 37844 KB Output is correct
7 Correct 28 ms 37880 KB Output is correct
8 Correct 23 ms 37888 KB Output is correct
9 Correct 275 ms 97208 KB Output is correct
10 Correct 52 ms 49724 KB Output is correct
11 Correct 93 ms 71684 KB Output is correct
12 Correct 45 ms 52200 KB Output is correct
13 Correct 54 ms 53412 KB Output is correct
14 Correct 21 ms 38228 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct
16 Correct 291 ms 97252 KB Output is correct
17 Correct 32 ms 44976 KB Output is correct
18 Incorrect 32 ms 45084 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 35 ms 45080 KB Output is correct
2 Correct 37 ms 45036 KB Output is correct
3 Correct 24 ms 37876 KB Output is correct
4 Correct 39 ms 45088 KB Output is correct
5 Correct 34 ms 45004 KB Output is correct
6 Correct 24 ms 37844 KB Output is correct
7 Correct 28 ms 37880 KB Output is correct
8 Correct 23 ms 37888 KB Output is correct
9 Correct 275 ms 97208 KB Output is correct
10 Correct 52 ms 49724 KB Output is correct
11 Correct 93 ms 71684 KB Output is correct
12 Correct 45 ms 52200 KB Output is correct
13 Correct 54 ms 53412 KB Output is correct
14 Correct 21 ms 38228 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct
16 Correct 291 ms 97252 KB Output is correct
17 Incorrect 695 ms 153348 KB Tree @(100001, 100001) appears more than once: for edges on positions 40708 and 140975
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 45080 KB Output is correct
2 Correct 37 ms 45036 KB Output is correct
3 Correct 24 ms 37876 KB Output is correct
4 Correct 39 ms 45088 KB Output is correct
5 Correct 34 ms 45004 KB Output is correct
6 Correct 24 ms 37844 KB Output is correct
7 Correct 28 ms 37880 KB Output is correct
8 Correct 23 ms 37888 KB Output is correct
9 Correct 275 ms 97208 KB Output is correct
10 Correct 52 ms 49724 KB Output is correct
11 Correct 93 ms 71684 KB Output is correct
12 Correct 45 ms 52200 KB Output is correct
13 Correct 54 ms 53412 KB Output is correct
14 Correct 21 ms 38228 KB Output is correct
15 Correct 24 ms 38556 KB Output is correct
16 Correct 291 ms 97252 KB Output is correct
17 Correct 41 ms 45012 KB Output is correct
18 Correct 33 ms 45088 KB Output is correct
19 Incorrect 33 ms 45096 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 4
20 Halted 0 ms 0 KB -