oj.uz

답안 #788494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788494 2023-07-20T09:28:01 Z alexander707070 분수 공원 (IOI21_parks) C++17
55 / 100
 1479 ms 178560 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;
map< pair<int,int>, vector<int> > bro;

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

void add(int x,int y,int z){
    for(int i=0;i<bro[{x,y}].size();i++){
        ors.push_back({op(bro[{x,y}][i]),op(z)});
    }
    bro[{x,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){
    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});
            
            br+=2;
        }
    }   

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

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

    for(int i=0;i<n;i++){
        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(){
    cout<<construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
*/

Compilation message

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 44996 KB Output is correct
2 Correct 28 ms 44972 KB Output is correct
3 Correct 18 ms 37788 KB Output is correct
4 Correct 28 ms 45048 KB Output is correct
5 Correct 29 ms 45052 KB Output is correct
6 Correct 19 ms 37844 KB Output is correct
7 Correct 19 ms 37772 KB Output is correct
8 Correct 20 ms 37864 KB Output is correct
9 Correct 451 ms 101352 KB Output is correct
10 Correct 45 ms 50380 KB Output is correct
11 Correct 139 ms 74188 KB Output is correct
12 Correct 55 ms 52940 KB Output is correct
13 Correct 77 ms 54720 KB Output is correct
14 Correct 24 ms 38268 KB Output is correct
15 Correct 22 ms 38596 KB Output is correct
16 Correct 397 ms 101224 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 44996 KB Output is correct
2 Correct 28 ms 44972 KB Output is correct
3 Correct 18 ms 37788 KB Output is correct
4 Correct 28 ms 45048 KB Output is correct
5 Correct 29 ms 45052 KB Output is correct
6 Correct 19 ms 37844 KB Output is correct
7 Correct 19 ms 37772 KB Output is correct
8 Correct 20 ms 37864 KB Output is correct
9 Correct 451 ms 101352 KB Output is correct
10 Correct 45 ms 50380 KB Output is correct
11 Correct 139 ms 74188 KB Output is correct
12 Correct 55 ms 52940 KB Output is correct
13 Correct 77 ms 54720 KB Output is correct
14 Correct 24 ms 38268 KB Output is correct
15 Correct 22 ms 38596 KB Output is correct
16 Correct 397 ms 101224 KB Output is correct
17 Correct 27 ms 44976 KB Output is correct
18 Correct 28 ms 45092 KB Output is correct
19 Correct 32 ms 45044 KB Output is correct
20 Correct 30 ms 45068 KB Output is correct
21 Correct 20 ms 37788 KB Output is correct
22 Correct 29 ms 45056 KB Output is correct
23 Correct 1449 ms 162480 KB Output is correct
24 Correct 30 ms 45040 KB Output is correct
25 Correct 34 ms 45692 KB Output is correct
26 Correct 24 ms 38564 KB Output is correct
27 Correct 24 ms 38860 KB Output is correct
28 Correct 404 ms 89020 KB Output is correct
29 Correct 651 ms 113800 KB Output is correct
30 Correct 1014 ms 137772 KB Output is correct
31 Correct 1377 ms 161452 KB Output is correct
32 Correct 27 ms 45012 KB Output is correct
33 Correct 28 ms 45016 KB Output is correct
34 Correct 27 ms 45012 KB Output is correct
35 Correct 20 ms 37888 KB Output is correct
36 Correct 20 ms 37812 KB Output is correct
37 Correct 29 ms 45012 KB Output is correct
38 Correct 28 ms 45004 KB Output is correct
39 Correct 27 ms 45052 KB Output is correct
40 Correct 30 ms 45004 KB Output is correct
41 Correct 18 ms 37880 KB Output is correct
42 Correct 28 ms 45012 KB Output is correct
43 Correct 21 ms 38484 KB Output is correct
44 Correct 22 ms 38684 KB Output is correct
45 Correct 516 ms 101424 KB Output is correct
46 Correct 925 ms 129148 KB Output is correct
47 Correct 885 ms 129224 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 44996 KB Output is correct
2 Correct 28 ms 44972 KB Output is correct
3 Correct 18 ms 37788 KB Output is correct
4 Correct 28 ms 45048 KB Output is correct
5 Correct 29 ms 45052 KB Output is correct
6 Correct 19 ms 37844 KB Output is correct
7 Correct 19 ms 37772 KB Output is correct
8 Correct 20 ms 37864 KB Output is correct
9 Correct 451 ms 101352 KB Output is correct
10 Correct 45 ms 50380 KB Output is correct
11 Correct 139 ms 74188 KB Output is correct
12 Correct 55 ms 52940 KB Output is correct
13 Correct 77 ms 54720 KB Output is correct
14 Correct 24 ms 38268 KB Output is correct
15 Correct 22 ms 38596 KB Output is correct
16 Correct 397 ms 101224 KB Output is correct
17 Correct 27 ms 44976 KB Output is correct
18 Correct 28 ms 45092 KB Output is correct
19 Correct 32 ms 45044 KB Output is correct
20 Correct 30 ms 45068 KB Output is correct
21 Correct 20 ms 37788 KB Output is correct
22 Correct 29 ms 45056 KB Output is correct
23 Correct 1449 ms 162480 KB Output is correct
24 Correct 30 ms 45040 KB Output is correct
25 Correct 34 ms 45692 KB Output is correct
26 Correct 24 ms 38564 KB Output is correct
27 Correct 24 ms 38860 KB Output is correct
28 Correct 404 ms 89020 KB Output is correct
29 Correct 651 ms 113800 KB Output is correct
30 Correct 1014 ms 137772 KB Output is correct
31 Correct 1377 ms 161452 KB Output is correct
32 Correct 27 ms 45012 KB Output is correct
33 Correct 28 ms 45016 KB Output is correct
34 Correct 27 ms 45012 KB Output is correct
35 Correct 20 ms 37888 KB Output is correct
36 Correct 20 ms 37812 KB Output is correct
37 Correct 29 ms 45012 KB Output is correct
38 Correct 28 ms 45004 KB Output is correct
39 Correct 27 ms 45052 KB Output is correct
40 Correct 30 ms 45004 KB Output is correct
41 Correct 18 ms 37880 KB Output is correct
42 Correct 28 ms 45012 KB Output is correct
43 Correct 21 ms 38484 KB Output is correct
44 Correct 22 ms 38684 KB Output is correct
45 Correct 516 ms 101424 KB Output is correct
46 Correct 925 ms 129148 KB Output is correct
47 Correct 885 ms 129224 KB Output is correct
48 Correct 33 ms 44956 KB Output is correct
49 Correct 28 ms 45016 KB Output is correct
50 Correct 29 ms 45032 KB Output is correct
51 Correct 30 ms 45060 KB Output is correct
52 Correct 29 ms 45048 KB Output is correct
53 Correct 30 ms 45040 KB Output is correct
54 Correct 31 ms 45000 KB Output is correct
55 Incorrect 1309 ms 162056 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 44996 KB Output is correct
2 Correct 28 ms 44972 KB Output is correct
3 Correct 18 ms 37788 KB Output is correct
4 Correct 28 ms 45048 KB Output is correct
5 Correct 29 ms 45052 KB Output is correct
6 Correct 19 ms 37844 KB Output is correct
7 Correct 19 ms 37772 KB Output is correct
8 Correct 20 ms 37864 KB Output is correct
9 Correct 451 ms 101352 KB Output is correct
10 Correct 45 ms 50380 KB Output is correct
11 Correct 139 ms 74188 KB Output is correct
12 Correct 55 ms 52940 KB Output is correct
13 Correct 77 ms 54720 KB Output is correct
14 Correct 24 ms 38268 KB Output is correct
15 Correct 22 ms 38596 KB Output is correct
16 Correct 397 ms 101224 KB Output is correct
17 Correct 29 ms 45052 KB Output is correct
18 Correct 29 ms 45072 KB Output is correct
19 Correct 19 ms 37860 KB Output is correct
20 Correct 1322 ms 178560 KB Output is correct
21 Correct 1407 ms 171268 KB Output is correct
22 Correct 1369 ms 166532 KB Output is correct
23 Correct 910 ms 143024 KB Output is correct
24 Correct 335 ms 79656 KB Output is correct
25 Correct 635 ms 112524 KB Output is correct
26 Correct 681 ms 112616 KB Output is correct
27 Correct 1081 ms 160560 KB Output is correct
28 Correct 1016 ms 160488 KB Output is correct
29 Correct 1041 ms 160716 KB Output is correct
30 Correct 1018 ms 160504 KB Output is correct
31 Correct 28 ms 45080 KB Output is correct
32 Correct 70 ms 52656 KB Output is correct
33 Correct 149 ms 58904 KB Output is correct
34 Correct 1436 ms 178420 KB Output is correct
35 Correct 36 ms 40708 KB Output is correct
36 Correct 141 ms 51684 KB Output is correct
37 Correct 308 ms 65048 KB Output is correct
38 Correct 467 ms 90156 KB Output is correct
39 Correct 596 ms 107208 KB Output is correct
40 Correct 893 ms 125784 KB Output is correct
41 Correct 1193 ms 143256 KB Output is correct
42 Correct 1444 ms 160960 KB Output is correct
43 Correct 29 ms 45024 KB Output is correct
44 Correct 33 ms 45004 KB Output is correct
45 Correct 30 ms 45028 KB Output is correct
46 Correct 20 ms 37952 KB Output is correct
47 Correct 19 ms 37884 KB Output is correct
48 Correct 29 ms 45068 KB Output is correct
49 Correct 28 ms 45028 KB Output is correct
50 Correct 29 ms 44976 KB Output is correct
51 Correct 38 ms 45008 KB Output is correct
52 Correct 19 ms 37844 KB Output is correct
53 Correct 29 ms 45060 KB Output is correct
54 Correct 22 ms 38484 KB Output is correct
55 Correct 27 ms 38692 KB Output is correct
56 Correct 482 ms 101536 KB Output is correct
57 Correct 826 ms 129224 KB Output is correct
58 Correct 939 ms 129136 KB Output is correct
59 Correct 20 ms 37888 KB Output is correct
60 Correct 35 ms 45040 KB Output is correct
61 Correct 19 ms 37844 KB Output is correct
62 Correct 1002 ms 160600 KB Output is correct
63 Correct 1000 ms 160660 KB Output is correct
64 Correct 1016 ms 160052 KB Output is correct
65 Correct 27 ms 38964 KB Output is correct
66 Correct 31 ms 40192 KB Output is correct
67 Correct 578 ms 101276 KB Output is correct
68 Correct 993 ms 131608 KB Output is correct
69 Correct 1377 ms 161216 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 44996 KB Output is correct
2 Correct 28 ms 44972 KB Output is correct
3 Correct 18 ms 37788 KB Output is correct
4 Correct 28 ms 45048 KB Output is correct
5 Correct 29 ms 45052 KB Output is correct
6 Correct 19 ms 37844 KB Output is correct
7 Correct 19 ms 37772 KB Output is correct
8 Correct 20 ms 37864 KB Output is correct
9 Correct 451 ms 101352 KB Output is correct
10 Correct 45 ms 50380 KB Output is correct
11 Correct 139 ms 74188 KB Output is correct
12 Correct 55 ms 52940 KB Output is correct
13 Correct 77 ms 54720 KB Output is correct
14 Correct 24 ms 38268 KB Output is correct
15 Correct 22 ms 38596 KB Output is correct
16 Correct 397 ms 101224 KB Output is correct
17 Correct 1022 ms 161424 KB Output is correct
18 Correct 1091 ms 161284 KB Output is correct
19 Correct 1479 ms 174704 KB Output is correct
20 Correct 1248 ms 153528 KB Output is correct
21 Correct 1139 ms 144840 KB Output is correct
22 Correct 32 ms 45024 KB Output is correct
23 Correct 140 ms 61632 KB Output is correct
24 Correct 57 ms 43616 KB Output is correct
25 Correct 184 ms 56884 KB Output is correct
26 Correct 400 ms 70016 KB Output is correct
27 Correct 531 ms 100096 KB Output is correct
28 Correct 709 ms 114352 KB Output is correct
29 Correct 921 ms 129948 KB Output is correct
30 Correct 1105 ms 143884 KB Output is correct
31 Correct 1345 ms 158540 KB Output is correct
32 Correct 1239 ms 158516 KB Output is correct
33 Correct 1032 ms 160492 KB Output is correct
34 Correct 26 ms 39368 KB Output is correct
35 Correct 32 ms 40456 KB Output is correct
36 Correct 531 ms 100544 KB Output is correct
37 Correct 928 ms 130536 KB Output is correct
38 Correct 1401 ms 160048 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 44996 KB Output is correct
2 Correct 28 ms 44972 KB Output is correct
3 Correct 18 ms 37788 KB Output is correct
4 Correct 28 ms 45048 KB Output is correct
5 Correct 29 ms 45052 KB Output is correct
6 Correct 19 ms 37844 KB Output is correct
7 Correct 19 ms 37772 KB Output is correct
8 Correct 20 ms 37864 KB Output is correct
9 Correct 451 ms 101352 KB Output is correct
10 Correct 45 ms 50380 KB Output is correct
11 Correct 139 ms 74188 KB Output is correct
12 Correct 55 ms 52940 KB Output is correct
13 Correct 77 ms 54720 KB Output is correct
14 Correct 24 ms 38268 KB Output is correct
15 Correct 22 ms 38596 KB Output is correct
16 Correct 397 ms 101224 KB Output is correct
17 Correct 27 ms 44976 KB Output is correct
18 Correct 28 ms 45092 KB Output is correct
19 Correct 32 ms 45044 KB Output is correct
20 Correct 30 ms 45068 KB Output is correct
21 Correct 20 ms 37788 KB Output is correct
22 Correct 29 ms 45056 KB Output is correct
23 Correct 1449 ms 162480 KB Output is correct
24 Correct 30 ms 45040 KB Output is correct
25 Correct 34 ms 45692 KB Output is correct
26 Correct 24 ms 38564 KB Output is correct
27 Correct 24 ms 38860 KB Output is correct
28 Correct 404 ms 89020 KB Output is correct
29 Correct 651 ms 113800 KB Output is correct
30 Correct 1014 ms 137772 KB Output is correct
31 Correct 1377 ms 161452 KB Output is correct
32 Correct 27 ms 45012 KB Output is correct
33 Correct 28 ms 45016 KB Output is correct
34 Correct 27 ms 45012 KB Output is correct
35 Correct 20 ms 37888 KB Output is correct
36 Correct 20 ms 37812 KB Output is correct
37 Correct 29 ms 45012 KB Output is correct
38 Correct 28 ms 45004 KB Output is correct
39 Correct 27 ms 45052 KB Output is correct
40 Correct 30 ms 45004 KB Output is correct
41 Correct 18 ms 37880 KB Output is correct
42 Correct 28 ms 45012 KB Output is correct
43 Correct 21 ms 38484 KB Output is correct
44 Correct 22 ms 38684 KB Output is correct
45 Correct 516 ms 101424 KB Output is correct
46 Correct 925 ms 129148 KB Output is correct
47 Correct 885 ms 129224 KB Output is correct
48 Correct 33 ms 44956 KB Output is correct
49 Correct 28 ms 45016 KB Output is correct
50 Correct 29 ms 45032 KB Output is correct
51 Correct 30 ms 45060 KB Output is correct
52 Correct 29 ms 45048 KB Output is correct
53 Correct 30 ms 45040 KB Output is correct
54 Correct 31 ms 45000 KB Output is correct
55 Incorrect 1309 ms 162056 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -