oj.uz

Submission #788471

# Submission time Handle Problem Language Result Execution time Memory
788471 2023-07-20T09:09:33 Z alexander707070 Fountain Parks (IOI21_parks) C++17
25 / 100
 1407 ms 173680 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,benches,br,k,comp[MAXN],ans[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;

map< pair<int,int>, int> mp;

void add(int x,int y,int z){
    if(mp.find({x,y})==mp.end()){
        mp[{x,y}]=z;
    }
}

int op(int x){
    if(x<400000)return x+400000;
    return x-400000;
}

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 construct_roads(vector<int> x,vector<int> y){
    n=int(x.size());

    for(int i=0;i<n;i++){
        mp[{x[i],y[i]}]=i+1;
    }

    br=0;
    for(int i=0;i<n;i++){
        curr=mp[{x[i]-2,y[i]}];
        if(curr!=0){
            curr--;
            add(x[i]-1,y[i]-1,br);
            add(x[i]-1,y[i]+1,br+1);

            ors.push_back({br,br+1});

            if(mp[{x[i]-1,y[i]-1}]!=br)ors.push_back({op(mp[{x[i]-1,y[i]-1}]),op(br)});
            if(mp[{x[i]-1,y[i]+1}]!=br+1)ors.push_back({op(mp[{x[i]-1,y[i]+1}]),op(br+1)});
            
            br+=2;
        }

        curr=mp[{x[i],y[i]-2}];
        if(curr!=0){
            curr--;
            add(x[i]-1,y[i]-1,br);
            add(x[i]+1,y[i]-1,br+1);
            ors.push_back({br,br+1});

            if(mp[{x[i]-1,y[i]-1}]!=br)ors.push_back({op(mp[{x[i]-1,y[i]-1}]),op(br)});
            if(mp[{x[i]+1,y[i]-1}]!=br+1)ors.push_back({op(mp[{x[i]+1,y[i]-1}]),op(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;
    }

    br=0;
    for(int i=0;i<n;i++){
        curr=mp[{x[i]-2,y[i]}];
        if(curr!=0){
            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;
        }

        curr=mp[{x[i],y[i]-2}];
        if(curr!=0){
            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(){
    construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
*/

Compilation message

parks.cpp: In function 'void dfs(int)':
parks.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'void scc(int)':
parks.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<r[x].size();i++){
      |                 ~^~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:89: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]
   89 |     for(int i=0;i<ors.size();i++){
      |                 ~^~~~~~~~~~~
parks.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 45064 KB Output is correct
2 Correct 27 ms 45056 KB Output is correct
3 Correct 17 ms 37884 KB Output is correct
4 Correct 26 ms 45060 KB Output is correct
5 Correct 28 ms 44940 KB Output is correct
6 Correct 18 ms 37888 KB Output is correct
7 Correct 17 ms 37880 KB Output is correct
8 Correct 17 ms 37860 KB Output is correct
9 Correct 398 ms 91428 KB Output is correct
10 Correct 43 ms 49296 KB Output is correct
11 Correct 141 ms 68904 KB Output is correct
12 Correct 54 ms 51452 KB Output is correct
13 Correct 91 ms 50308 KB Output is correct
14 Correct 19 ms 38100 KB Output is correct
15 Correct 23 ms 38452 KB Output is correct
16 Correct 563 ms 91420 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 45064 KB Output is correct
2 Correct 27 ms 45056 KB Output is correct
3 Correct 17 ms 37884 KB Output is correct
4 Correct 26 ms 45060 KB Output is correct
5 Correct 28 ms 44940 KB Output is correct
6 Correct 18 ms 37888 KB Output is correct
7 Correct 17 ms 37880 KB Output is correct
8 Correct 17 ms 37860 KB Output is correct
9 Correct 398 ms 91428 KB Output is correct
10 Correct 43 ms 49296 KB Output is correct
11 Correct 141 ms 68904 KB Output is correct
12 Correct 54 ms 51452 KB Output is correct
13 Correct 91 ms 50308 KB Output is correct
14 Correct 19 ms 38100 KB Output is correct
15 Correct 23 ms 38452 KB Output is correct
16 Correct 563 ms 91420 KB Output is correct
17 Incorrect 19 ms 37768 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 45064 KB Output is correct
2 Correct 27 ms 45056 KB Output is correct
3 Correct 17 ms 37884 KB Output is correct
4 Correct 26 ms 45060 KB Output is correct
5 Correct 28 ms 44940 KB Output is correct
6 Correct 18 ms 37888 KB Output is correct
7 Correct 17 ms 37880 KB Output is correct
8 Correct 17 ms 37860 KB Output is correct
9 Correct 398 ms 91428 KB Output is correct
10 Correct 43 ms 49296 KB Output is correct
11 Correct 141 ms 68904 KB Output is correct
12 Correct 54 ms 51452 KB Output is correct
13 Correct 91 ms 50308 KB Output is correct
14 Correct 19 ms 38100 KB Output is correct
15 Correct 23 ms 38452 KB Output is correct
16 Correct 563 ms 91420 KB Output is correct
17 Incorrect 19 ms 37768 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 45064 KB Output is correct
2 Correct 27 ms 45056 KB Output is correct
3 Correct 17 ms 37884 KB Output is correct
4 Correct 26 ms 45060 KB Output is correct
5 Correct 28 ms 44940 KB Output is correct
6 Correct 18 ms 37888 KB Output is correct
7 Correct 17 ms 37880 KB Output is correct
8 Correct 17 ms 37860 KB Output is correct
9 Correct 398 ms 91428 KB Output is correct
10 Correct 43 ms 49296 KB Output is correct
11 Correct 141 ms 68904 KB Output is correct
12 Correct 54 ms 51452 KB Output is correct
13 Correct 91 ms 50308 KB Output is correct
14 Correct 19 ms 38100 KB Output is correct
15 Correct 23 ms 38452 KB Output is correct
16 Correct 563 ms 91420 KB Output is correct
17 Correct 37 ms 45000 KB Output is correct
18 Correct 34 ms 44956 KB Output is correct
19 Correct 24 ms 37828 KB Output is correct
20 Correct 1148 ms 170400 KB Output is correct
21 Correct 1407 ms 163284 KB Output is correct
22 Correct 1103 ms 158216 KB Output is correct
23 Correct 817 ms 127740 KB Output is correct
24 Correct 498 ms 80252 KB Output is correct
25 Correct 753 ms 94152 KB Output is correct
26 Correct 724 ms 94164 KB Output is correct
27 Correct 1137 ms 142228 KB Output is correct
28 Correct 1106 ms 142276 KB Output is correct
29 Correct 1120 ms 142324 KB Output is correct
30 Correct 1117 ms 142272 KB Output is correct
31 Correct 31 ms 44992 KB Output is correct
32 Correct 71 ms 51756 KB Output is correct
33 Correct 129 ms 59428 KB Output is correct
34 Correct 1140 ms 173680 KB Output is correct
35 Correct 35 ms 40176 KB Output is correct
36 Correct 114 ms 48820 KB Output is correct
37 Correct 297 ms 59800 KB Output is correct
38 Correct 385 ms 85988 KB Output is correct
39 Correct 564 ms 101636 KB Output is correct
40 Correct 758 ms 118780 KB Output is correct
41 Correct 1035 ms 134776 KB Output is correct
42 Correct 1265 ms 151208 KB Output is correct
43 Correct 38 ms 45048 KB Output is correct
44 Correct 32 ms 45032 KB Output is correct
45 Correct 32 ms 45060 KB Output is correct
46 Correct 20 ms 37836 KB Output is correct
47 Correct 20 ms 37880 KB Output is correct
48 Correct 31 ms 45052 KB Output is correct
49 Correct 35 ms 45044 KB Output is correct
50 Correct 33 ms 45012 KB Output is correct
51 Correct 31 ms 45036 KB Output is correct
52 Correct 20 ms 37780 KB Output is correct
53 Correct 30 ms 45056 KB Output is correct
54 Correct 26 ms 38268 KB Output is correct
55 Correct 24 ms 38572 KB Output is correct
56 Correct 496 ms 95212 KB Output is correct
57 Correct 775 ms 119976 KB Output is correct
58 Correct 797 ms 120112 KB Output is correct
59 Correct 21 ms 37844 KB Output is correct
60 Correct 31 ms 45012 KB Output is correct
61 Correct 21 ms 37784 KB Output is correct
62 Correct 1158 ms 142260 KB Output is correct
63 Correct 1167 ms 142280 KB Output is correct
64 Correct 1085 ms 141900 KB Output is correct
65 Correct 30 ms 38788 KB Output is correct
66 Correct 31 ms 39700 KB Output is correct
67 Correct 477 ms 94940 KB Output is correct
68 Correct 843 ms 122604 KB Output is correct
69 Correct 1232 ms 149184 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 45064 KB Output is correct
2 Correct 27 ms 45056 KB Output is correct
3 Correct 17 ms 37884 KB Output is correct
4 Correct 26 ms 45060 KB Output is correct
5 Correct 28 ms 44940 KB Output is correct
6 Correct 18 ms 37888 KB Output is correct
7 Correct 17 ms 37880 KB Output is correct
8 Correct 17 ms 37860 KB Output is correct
9 Correct 398 ms 91428 KB Output is correct
10 Correct 43 ms 49296 KB Output is correct
11 Correct 141 ms 68904 KB Output is correct
12 Correct 54 ms 51452 KB Output is correct
13 Correct 91 ms 50308 KB Output is correct
14 Correct 19 ms 38100 KB Output is correct
15 Correct 23 ms 38452 KB Output is correct
16 Correct 563 ms 91420 KB Output is correct
17 Incorrect 575 ms 93764 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 45064 KB Output is correct
2 Correct 27 ms 45056 KB Output is correct
3 Correct 17 ms 37884 KB Output is correct
4 Correct 26 ms 45060 KB Output is correct
5 Correct 28 ms 44940 KB Output is correct
6 Correct 18 ms 37888 KB Output is correct
7 Correct 17 ms 37880 KB Output is correct
8 Correct 17 ms 37860 KB Output is correct
9 Correct 398 ms 91428 KB Output is correct
10 Correct 43 ms 49296 KB Output is correct
11 Correct 141 ms 68904 KB Output is correct
12 Correct 54 ms 51452 KB Output is correct
13 Correct 91 ms 50308 KB Output is correct
14 Correct 19 ms 38100 KB Output is correct
15 Correct 23 ms 38452 KB Output is correct
16 Correct 563 ms 91420 KB Output is correct
17 Incorrect 19 ms 37768 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -