oj.uz

Submission #814292

# Submission time Handle Problem Language Result Execution time Memory
814292 2023-08-08T06:42:34 Z alvingogo Fountain Parks (IOI21_parks) C++17
45 / 100
 1414 ms 113088 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
    vector<int> bo,ss;
    void init(int x){
        bo.resize(x);
        ss.resize(x,1);
        iota(bo.begin(),bo.end(),0);
    }  
    int find(int x){
        return bo[x]==x?x:bo[x]=find(bo[x]);
    }
    int merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return 0;
        }
        bo[x]=y;
        ss[y]+=ss[x];
        return 1;
    }
}dsu;
vector<int> au,av,aa,ab;
void ag(int a,int b,int c,int d){
    au.push_back(a);
    av.push_back(b);
    aa.push_back(c);
    ab.push_back(d);
}
map<pair<int,int>,int> pt,cn;
vector<pair<int,int> > tl;
vector<vector<int> > eg;
vector<int> se,vis;
int cnt=0;
void add(pair<int,int> a,pair<int,int> x){
    if(a.fs>a.sc){
        swap(a.fs,a.sc);
    }
    if(cn.find(a)==cn.end()){
        cn[a]=cnt;
        cnt++;
        eg.push_back(vector<int>());
        tl.push_back(a);
        se.push_back(0);
    }
    if(pt.find(x)==pt.end()){
        pt[x]=cnt;
        cnt++;
        eg.push_back(vector<int>());
        tl.push_back(x);
        se.push_back(1);
    }
    //cout << cn[a] << " " << pt[x] << "\n";
    eg[cn[a]].push_back(pt[x]);
    eg[pt[x]].push_back(cn[a]);
}
void dfs(int r){
    vis[r]=1;
    int p=0;
    for(auto h:eg[r]){
        if(vis[h]==0){
            vis[h]=1;
            p=h;
            ag(tl[r].fs,tl[r].sc,tl[h].fs,tl[h].sc);
            break;
        }
    }
    for(auto h:eg[p]){
        if(vis[h]==0){
            dfs(h);
            break;
        }
    }
}
int construct_roads(vector<int> x, vector<int> y) {
    cn.clear();
    pt.clear();
    eg.clear();
    se.clear();
    tl.clear();
    vis.clear();
    cnt=0;
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    map<pair<int,int>,int> mp;
    int n=x.size();
    for(int i=0;i<n;i++){
        mp[{x[i],y[i]}]=i;
    }
    dsu.init(n);
    const int dx[4]={0,0,2,-2},dy[4]={2,-2,0,0};
    for(int p=0;p<n;p++){
        for(int k=0;k<4;k++){
            int c=x[p]+dx[k],d=y[p]+dy[k];
            if(mp.find({c,d})!=mp.end()){
                int a=mp[{c,d}];
                if(dsu.merge(a,p)){
                    if(x[a]==x[p]){
                        int u=(y[a]+y[p])/2;
                        add({a,p},{x[a]-1,u});
                        add({a,p},{x[a]+1,u});
                    }
                    else{
                        int u=(x[a]+x[p])/2;
                        add({a,p},{u,y[a]-1});
                        add({a,p},{u,y[a]+1});
                    }
                }
            }
        }
    }
    if(dsu.ss[dsu.find(0)]!=n){
        return 0;
    }
    vis.resize(cnt);
    for(int i=0;i<cnt;i++){
        if(se[i]==0 && !vis[i]){
            dfs(i);
        }
    }
    build(au,av,aa,ab);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 500 ms 55956 KB Output is correct
10 Correct 23 ms 5900 KB Output is correct
11 Correct 162 ms 30144 KB Output is correct
12 Correct 34 ms 8576 KB Output is correct
13 Correct 109 ms 24056 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 472 ms 56032 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 500 ms 55956 KB Output is correct
10 Correct 23 ms 5900 KB Output is correct
11 Correct 162 ms 30144 KB Output is correct
12 Correct 34 ms 8576 KB Output is correct
13 Correct 109 ms 24056 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 472 ms 56032 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 1158 ms 90392 KB Given structure is not connected: There is no path between vertices 0 and 1
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 500 ms 55956 KB Output is correct
10 Correct 23 ms 5900 KB Output is correct
11 Correct 162 ms 30144 KB Output is correct
12 Correct 34 ms 8576 KB Output is correct
13 Correct 109 ms 24056 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 472 ms 56032 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 1158 ms 90392 KB Given structure is not connected: There is no path between vertices 0 and 1
24 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 500 ms 55956 KB Output is correct
10 Correct 23 ms 5900 KB Output is correct
11 Correct 162 ms 30144 KB Output is correct
12 Correct 34 ms 8576 KB Output is correct
13 Correct 109 ms 24056 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 472 ms 56032 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1099 ms 85548 KB Output is correct
21 Correct 1083 ms 85584 KB Output is correct
22 Correct 1085 ms 85520 KB Output is correct
23 Correct 888 ms 95236 KB Output is correct
24 Correct 255 ms 18208 KB Output is correct
25 Correct 1116 ms 98056 KB Output is correct
26 Correct 1110 ms 98096 KB Output is correct
27 Correct 1184 ms 112532 KB Output is correct
28 Correct 1140 ms 112560 KB Output is correct
29 Correct 1205 ms 112488 KB Output is correct
30 Correct 1161 ms 112560 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 42 ms 6980 KB Output is correct
33 Correct 92 ms 9540 KB Output is correct
34 Correct 1000 ms 85928 KB Output is correct
35 Correct 26 ms 4108 KB Output is correct
36 Correct 173 ms 19276 KB Output is correct
37 Correct 435 ms 37880 KB Output is correct
38 Correct 372 ms 37320 KB Output is correct
39 Correct 550 ms 49932 KB Output is correct
40 Correct 765 ms 65372 KB Output is correct
41 Correct 1016 ms 77948 KB Output is correct
42 Correct 1253 ms 90764 KB Output is correct
43 Correct 1 ms 296 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 300 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 296 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 4 ms 1108 KB Output is correct
55 Correct 7 ms 1492 KB Output is correct
56 Correct 468 ms 47716 KB Output is correct
57 Correct 795 ms 70316 KB Output is correct
58 Correct 770 ms 70184 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 1 ms 212 KB Output is correct
62 Correct 1247 ms 112760 KB Output is correct
63 Correct 1183 ms 112672 KB Output is correct
64 Correct 1361 ms 112196 KB Output is correct
65 Correct 9 ms 1876 KB Output is correct
66 Correct 20 ms 3492 KB Output is correct
67 Correct 614 ms 46948 KB Output is correct
68 Correct 962 ms 71396 KB Output is correct
69 Correct 1414 ms 93312 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 500 ms 55956 KB Output is correct
10 Correct 23 ms 5900 KB Output is correct
11 Correct 162 ms 30144 KB Output is correct
12 Correct 34 ms 8576 KB Output is correct
13 Correct 109 ms 24056 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 472 ms 56032 KB Output is correct
17 Correct 1204 ms 112276 KB Output is correct
18 Correct 1182 ms 113088 KB Output is correct
19 Correct 1099 ms 85476 KB Output is correct
20 Correct 1247 ms 88596 KB Output is correct
21 Correct 1103 ms 89532 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 111 ms 15188 KB Output is correct
24 Correct 58 ms 8048 KB Output is correct
25 Correct 297 ms 27460 KB Output is correct
26 Correct 601 ms 51124 KB Output is correct
27 Correct 531 ms 46316 KB Output is correct
28 Correct 663 ms 58176 KB Output is correct
29 Correct 839 ms 70648 KB Output is correct
30 Correct 1070 ms 80944 KB Output is correct
31 Correct 1232 ms 91908 KB Output is correct
32 Correct 1147 ms 96364 KB Output is correct
33 Correct 1089 ms 112692 KB Output is correct
34 Correct 11 ms 2292 KB Output is correct
35 Correct 22 ms 3916 KB Output is correct
36 Correct 478 ms 47144 KB Output is correct
37 Correct 808 ms 71988 KB Output is correct
38 Correct 1193 ms 93924 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 500 ms 55956 KB Output is correct
10 Correct 23 ms 5900 KB Output is correct
11 Correct 162 ms 30144 KB Output is correct
12 Correct 34 ms 8576 KB Output is correct
13 Correct 109 ms 24056 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 472 ms 56032 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 1158 ms 90392 KB Given structure is not connected: There is no path between vertices 0 and 1
24 Halted 0 ms 0 KB -