oj.uz

Submission #788476

# Submission time Handle Problem Language Result Execution time Memory
788476 2023-07-20T09:13:53 Z alexander707070 Fountain Parks (IOI21_parks) C++17
45 / 100
 1476 ms 172240 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],dsu[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 root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    dsu[root(x)]=root(y);
}

int construct_roads(vector<int> x,vector<int> y){
    n=int(x.size());

    for(int i=0;i<n;i++){
        dsu[i]=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 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});

            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 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});

            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;
    }

    for(int i=0;i<n;i++)dsu[i]=i;

    br=0;
    for(int i=0;i<n;i++){
        curr=mp[{x[i]-2,y[i]}];
        if(curr!=0 and root(i)!=root(curr-1)){
            curr--; mergev(i,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 and root(i)!=root(curr-1)){
            curr--; mergev(i,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:101: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]
  101 |     for(int i=0;i<ors.size();i++){
      |                 ~^~~~~~~~~~~
parks.cpp:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i=0;i<sol.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 45044 KB Output is correct
2 Correct 26 ms 45008 KB Output is correct
3 Correct 18 ms 37828 KB Output is correct
4 Correct 25 ms 45012 KB Output is correct
5 Correct 30 ms 45052 KB Output is correct
6 Correct 17 ms 37888 KB Output is correct
7 Correct 18 ms 37844 KB Output is correct
8 Correct 18 ms 37844 KB Output is correct
9 Correct 432 ms 91592 KB Output is correct
10 Correct 46 ms 49356 KB Output is correct
11 Correct 144 ms 68764 KB Output is correct
12 Correct 55 ms 51572 KB Output is correct
13 Correct 77 ms 50216 KB Output is correct
14 Correct 18 ms 38140 KB Output is correct
15 Correct 20 ms 38432 KB Output is correct
16 Correct 468 ms 91356 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 45044 KB Output is correct
2 Correct 26 ms 45008 KB Output is correct
3 Correct 18 ms 37828 KB Output is correct
4 Correct 25 ms 45012 KB Output is correct
5 Correct 30 ms 45052 KB Output is correct
6 Correct 17 ms 37888 KB Output is correct
7 Correct 18 ms 37844 KB Output is correct
8 Correct 18 ms 37844 KB Output is correct
9 Correct 432 ms 91592 KB Output is correct
10 Correct 46 ms 49356 KB Output is correct
11 Correct 144 ms 68764 KB Output is correct
12 Correct 55 ms 51572 KB Output is correct
13 Correct 77 ms 50216 KB Output is correct
14 Correct 18 ms 38140 KB Output is correct
15 Correct 20 ms 38432 KB Output is correct
16 Correct 468 ms 91356 KB Output is correct
17 Correct 26 ms 45012 KB Output is correct
18 Correct 26 ms 45076 KB Output is correct
19 Correct 26 ms 45044 KB Output is correct
20 Correct 26 ms 45056 KB Output is correct
21 Correct 17 ms 37852 KB Output is correct
22 Correct 34 ms 45132 KB Output is correct
23 Incorrect 1164 ms 143884 KB Tree @(3, 104665) appears more than once: for edges on positions 14714 and 20642
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 45044 KB Output is correct
2 Correct 26 ms 45008 KB Output is correct
3 Correct 18 ms 37828 KB Output is correct
4 Correct 25 ms 45012 KB Output is correct
5 Correct 30 ms 45052 KB Output is correct
6 Correct 17 ms 37888 KB Output is correct
7 Correct 18 ms 37844 KB Output is correct
8 Correct 18 ms 37844 KB Output is correct
9 Correct 432 ms 91592 KB Output is correct
10 Correct 46 ms 49356 KB Output is correct
11 Correct 144 ms 68764 KB Output is correct
12 Correct 55 ms 51572 KB Output is correct
13 Correct 77 ms 50216 KB Output is correct
14 Correct 18 ms 38140 KB Output is correct
15 Correct 20 ms 38432 KB Output is correct
16 Correct 468 ms 91356 KB Output is correct
17 Correct 26 ms 45012 KB Output is correct
18 Correct 26 ms 45076 KB Output is correct
19 Correct 26 ms 45044 KB Output is correct
20 Correct 26 ms 45056 KB Output is correct
21 Correct 17 ms 37852 KB Output is correct
22 Correct 34 ms 45132 KB Output is correct
23 Incorrect 1164 ms 143884 KB Tree @(3, 104665) appears more than once: for edges on positions 14714 and 20642
24 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 45044 KB Output is correct
2 Correct 26 ms 45008 KB Output is correct
3 Correct 18 ms 37828 KB Output is correct
4 Correct 25 ms 45012 KB Output is correct
5 Correct 30 ms 45052 KB Output is correct
6 Correct 17 ms 37888 KB Output is correct
7 Correct 18 ms 37844 KB Output is correct
8 Correct 18 ms 37844 KB Output is correct
9 Correct 432 ms 91592 KB Output is correct
10 Correct 46 ms 49356 KB Output is correct
11 Correct 144 ms 68764 KB Output is correct
12 Correct 55 ms 51572 KB Output is correct
13 Correct 77 ms 50216 KB Output is correct
14 Correct 18 ms 38140 KB Output is correct
15 Correct 20 ms 38432 KB Output is correct
16 Correct 468 ms 91356 KB Output is correct
17 Correct 26 ms 44992 KB Output is correct
18 Correct 25 ms 44984 KB Output is correct
19 Correct 16 ms 37884 KB Output is correct
20 Correct 1004 ms 168692 KB Output is correct
21 Correct 1226 ms 161816 KB Output is correct
22 Correct 1062 ms 156708 KB Output is correct
23 Correct 767 ms 126720 KB Output is correct
24 Correct 378 ms 79276 KB Output is correct
25 Correct 676 ms 93372 KB Output is correct
26 Correct 655 ms 93388 KB Output is correct
27 Correct 1094 ms 141512 KB Output is correct
28 Correct 1076 ms 141580 KB Output is correct
29 Correct 1051 ms 141428 KB Output is correct
30 Correct 1022 ms 141452 KB Output is correct
31 Correct 26 ms 45012 KB Output is correct
32 Correct 65 ms 51640 KB Output is correct
33 Correct 130 ms 58604 KB Output is correct
34 Correct 1113 ms 171996 KB Output is correct
35 Correct 33 ms 40056 KB Output is correct
36 Correct 109 ms 48420 KB Output is correct
37 Correct 253 ms 58996 KB Output is correct
38 Correct 350 ms 85244 KB Output is correct
39 Correct 558 ms 100656 KB Output is correct
40 Correct 780 ms 117580 KB Output is correct
41 Correct 987 ms 133304 KB Output is correct
42 Correct 1251 ms 149516 KB Output is correct
43 Correct 26 ms 45044 KB Output is correct
44 Correct 29 ms 45052 KB Output is correct
45 Correct 26 ms 45004 KB Output is correct
46 Correct 17 ms 37820 KB Output is correct
47 Correct 18 ms 37844 KB Output is correct
48 Correct 27 ms 45012 KB Output is correct
49 Correct 27 ms 44992 KB Output is correct
50 Correct 27 ms 45012 KB Output is correct
51 Correct 27 ms 45028 KB Output is correct
52 Correct 18 ms 37824 KB Output is correct
53 Correct 27 ms 45076 KB Output is correct
54 Correct 20 ms 38356 KB Output is correct
55 Correct 21 ms 38484 KB Output is correct
56 Correct 489 ms 94728 KB Output is correct
57 Correct 850 ms 119432 KB Output is correct
58 Correct 798 ms 119364 KB Output is correct
59 Correct 17 ms 37844 KB Output is correct
60 Correct 27 ms 45000 KB Output is correct
61 Correct 18 ms 37848 KB Output is correct
62 Correct 1104 ms 141480 KB Output is correct
63 Correct 1114 ms 141452 KB Output is correct
64 Correct 1115 ms 140960 KB Output is correct
65 Correct 25 ms 38740 KB Output is correct
66 Correct 31 ms 39668 KB Output is correct
67 Correct 479 ms 94556 KB Output is correct
68 Correct 841 ms 121940 KB Output is correct
69 Correct 1217 ms 148392 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 45044 KB Output is correct
2 Correct 26 ms 45008 KB Output is correct
3 Correct 18 ms 37828 KB Output is correct
4 Correct 25 ms 45012 KB Output is correct
5 Correct 30 ms 45052 KB Output is correct
6 Correct 17 ms 37888 KB Output is correct
7 Correct 18 ms 37844 KB Output is correct
8 Correct 18 ms 37844 KB Output is correct
9 Correct 432 ms 91592 KB Output is correct
10 Correct 46 ms 49356 KB Output is correct
11 Correct 144 ms 68764 KB Output is correct
12 Correct 55 ms 51572 KB Output is correct
13 Correct 77 ms 50216 KB Output is correct
14 Correct 18 ms 38140 KB Output is correct
15 Correct 20 ms 38432 KB Output is correct
16 Correct 468 ms 91356 KB Output is correct
17 Correct 980 ms 141888 KB Output is correct
18 Correct 1051 ms 144188 KB Output is correct
19 Correct 1133 ms 172240 KB Output is correct
20 Correct 1091 ms 143664 KB Output is correct
21 Correct 962 ms 132452 KB Output is correct
22 Correct 29 ms 45012 KB Output is correct
23 Correct 124 ms 59784 KB Output is correct
24 Correct 50 ms 42312 KB Output is correct
25 Correct 156 ms 53008 KB Output is correct
26 Correct 319 ms 63828 KB Output is correct
27 Correct 471 ms 95080 KB Output is correct
28 Correct 649 ms 108544 KB Output is correct
29 Correct 805 ms 123272 KB Output is correct
30 Correct 1040 ms 135336 KB Output is correct
31 Correct 1220 ms 149248 KB Output is correct
32 Correct 1476 ms 146052 KB Output is correct
33 Correct 1240 ms 143280 KB Output is correct
34 Correct 30 ms 39060 KB Output is correct
35 Correct 35 ms 40020 KB Output is correct
36 Correct 537 ms 94684 KB Output is correct
37 Correct 838 ms 122144 KB Output is correct
38 Correct 1283 ms 148656 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 45044 KB Output is correct
2 Correct 26 ms 45008 KB Output is correct
3 Correct 18 ms 37828 KB Output is correct
4 Correct 25 ms 45012 KB Output is correct
5 Correct 30 ms 45052 KB Output is correct
6 Correct 17 ms 37888 KB Output is correct
7 Correct 18 ms 37844 KB Output is correct
8 Correct 18 ms 37844 KB Output is correct
9 Correct 432 ms 91592 KB Output is correct
10 Correct 46 ms 49356 KB Output is correct
11 Correct 144 ms 68764 KB Output is correct
12 Correct 55 ms 51572 KB Output is correct
13 Correct 77 ms 50216 KB Output is correct
14 Correct 18 ms 38140 KB Output is correct
15 Correct 20 ms 38432 KB Output is correct
16 Correct 468 ms 91356 KB Output is correct
17 Correct 26 ms 45012 KB Output is correct
18 Correct 26 ms 45076 KB Output is correct
19 Correct 26 ms 45044 KB Output is correct
20 Correct 26 ms 45056 KB Output is correct
21 Correct 17 ms 37852 KB Output is correct
22 Correct 34 ms 45132 KB Output is correct
23 Incorrect 1164 ms 143884 KB Tree @(3, 104665) appears more than once: for edges on positions 14714 and 20642
24 Halted 0 ms 0 KB -