oj.uz

Submission #814306

# Submission time Handle Problem Language Result Execution time Memory
814306 2023-08-08T06:45:39 Z alvingogo Fountain Parks (IOI21_parks) C++17
55 / 100
 1333 ms 112512 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);
        }
    }
}
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 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 454 ms 56168 KB Output is correct
10 Correct 25 ms 5816 KB Output is correct
11 Correct 155 ms 30132 KB Output is correct
12 Correct 36 ms 8664 KB Output is correct
13 Correct 108 ms 24124 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 473 ms 56036 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 454 ms 56168 KB Output is correct
10 Correct 25 ms 5816 KB Output is correct
11 Correct 155 ms 30132 KB Output is correct
12 Correct 36 ms 8664 KB Output is correct
13 Correct 108 ms 24124 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 473 ms 56036 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1124 ms 90556 KB Output is correct
24 Correct 1 ms 300 KB Output is correct
25 Correct 3 ms 852 KB Output is correct
26 Correct 6 ms 1364 KB Output is correct
27 Correct 9 ms 1900 KB Output is correct
28 Correct 321 ms 37048 KB Output is correct
29 Correct 616 ms 56048 KB Output is correct
30 Correct 828 ms 73844 KB Output is correct
31 Correct 1113 ms 90820 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 296 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 304 KB Output is correct
39 Correct 1 ms 300 KB Output is correct
40 Correct 0 ms 296 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 304 KB Output is correct
43 Correct 4 ms 1108 KB Output is correct
44 Correct 6 ms 1492 KB Output is correct
45 Correct 467 ms 47296 KB Output is correct
46 Correct 761 ms 69880 KB Output is correct
47 Correct 776 ms 69860 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 454 ms 56168 KB Output is correct
10 Correct 25 ms 5816 KB Output is correct
11 Correct 155 ms 30132 KB Output is correct
12 Correct 36 ms 8664 KB Output is correct
13 Correct 108 ms 24124 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 473 ms 56036 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1124 ms 90556 KB Output is correct
24 Correct 1 ms 300 KB Output is correct
25 Correct 3 ms 852 KB Output is correct
26 Correct 6 ms 1364 KB Output is correct
27 Correct 9 ms 1900 KB Output is correct
28 Correct 321 ms 37048 KB Output is correct
29 Correct 616 ms 56048 KB Output is correct
30 Correct 828 ms 73844 KB Output is correct
31 Correct 1113 ms 90820 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 296 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 304 KB Output is correct
39 Correct 1 ms 300 KB Output is correct
40 Correct 0 ms 296 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 304 KB Output is correct
43 Correct 4 ms 1108 KB Output is correct
44 Correct 6 ms 1492 KB Output is correct
45 Correct 467 ms 47296 KB Output is correct
46 Correct 761 ms 69880 KB Output is correct
47 Correct 776 ms 69860 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 300 KB Output is correct
50 Correct 1 ms 288 KB Output is correct
51 Incorrect 1 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 3
52 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 454 ms 56168 KB Output is correct
10 Correct 25 ms 5816 KB Output is correct
11 Correct 155 ms 30132 KB Output is correct
12 Correct 36 ms 8664 KB Output is correct
13 Correct 108 ms 24124 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 473 ms 56036 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1047 ms 91064 KB Output is correct
21 Correct 1059 ms 86532 KB Output is correct
22 Correct 1064 ms 86716 KB Output is correct
23 Correct 874 ms 94508 KB Output is correct
24 Correct 312 ms 17516 KB Output is correct
25 Correct 1192 ms 97580 KB Output is correct
26 Correct 1075 ms 97500 KB Output is correct
27 Correct 1144 ms 111784 KB Output is correct
28 Correct 1129 ms 111748 KB Output is correct
29 Correct 1186 ms 111800 KB Output is correct
30 Correct 1248 ms 111744 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 42 ms 6824 KB Output is correct
33 Correct 87 ms 8868 KB Output is correct
34 Correct 1040 ms 89752 KB Output is correct
35 Correct 28 ms 3992 KB Output is correct
36 Correct 217 ms 18824 KB Output is correct
37 Correct 507 ms 37312 KB Output is correct
38 Correct 424 ms 36564 KB Output is correct
39 Correct 631 ms 49280 KB Output is correct
40 Correct 905 ms 64464 KB Output is correct
41 Correct 1124 ms 77176 KB Output is correct
42 Correct 1333 ms 89864 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 0 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 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 4 ms 1108 KB Output is correct
55 Correct 6 ms 1412 KB Output is correct
56 Correct 450 ms 47000 KB Output is correct
57 Correct 895 ms 69544 KB Output is correct
58 Correct 855 ms 69452 KB Output is correct
59 Correct 0 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 0 ms 212 KB Output is correct
62 Correct 1191 ms 111968 KB Output is correct
63 Correct 1098 ms 111912 KB Output is correct
64 Correct 1148 ms 111544 KB Output is correct
65 Correct 9 ms 1876 KB Output is correct
66 Correct 24 ms 3460 KB Output is correct
67 Correct 477 ms 46232 KB Output is correct
68 Correct 822 ms 70688 KB Output is correct
69 Correct 1220 ms 92624 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 454 ms 56168 KB Output is correct
10 Correct 25 ms 5816 KB Output is correct
11 Correct 155 ms 30132 KB Output is correct
12 Correct 36 ms 8664 KB Output is correct
13 Correct 108 ms 24124 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 473 ms 56036 KB Output is correct
17 Correct 1100 ms 112424 KB Output is correct
18 Correct 1095 ms 112512 KB Output is correct
19 Correct 1094 ms 86092 KB Output is correct
20 Correct 1149 ms 87840 KB Output is correct
21 Correct 1167 ms 88800 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 114 ms 14764 KB Output is correct
24 Correct 57 ms 7844 KB Output is correct
25 Correct 268 ms 26872 KB Output is correct
26 Correct 588 ms 50584 KB Output is correct
27 Correct 516 ms 45568 KB Output is correct
28 Correct 693 ms 57376 KB Output is correct
29 Correct 853 ms 69732 KB Output is correct
30 Correct 1002 ms 80088 KB Output is correct
31 Correct 1177 ms 90940 KB Output is correct
32 Correct 1192 ms 95608 KB Output is correct
33 Correct 1101 ms 111904 KB Output is correct
34 Correct 11 ms 2192 KB Output is correct
35 Correct 22 ms 3848 KB Output is correct
36 Correct 485 ms 46572 KB Output is correct
37 Correct 812 ms 71260 KB Output is correct
38 Correct 1207 ms 93172 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 454 ms 56168 KB Output is correct
10 Correct 25 ms 5816 KB Output is correct
11 Correct 155 ms 30132 KB Output is correct
12 Correct 36 ms 8664 KB Output is correct
13 Correct 108 ms 24124 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 473 ms 56036 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1124 ms 90556 KB Output is correct
24 Correct 1 ms 300 KB Output is correct
25 Correct 3 ms 852 KB Output is correct
26 Correct 6 ms 1364 KB Output is correct
27 Correct 9 ms 1900 KB Output is correct
28 Correct 321 ms 37048 KB Output is correct
29 Correct 616 ms 56048 KB Output is correct
30 Correct 828 ms 73844 KB Output is correct
31 Correct 1113 ms 90820 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 296 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 0 ms 304 KB Output is correct
39 Correct 1 ms 300 KB Output is correct
40 Correct 0 ms 296 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 0 ms 304 KB Output is correct
43 Correct 4 ms 1108 KB Output is correct
44 Correct 6 ms 1492 KB Output is correct
45 Correct 467 ms 47296 KB Output is correct
46 Correct 761 ms 69880 KB Output is correct
47 Correct 776 ms 69860 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 300 KB Output is correct
50 Correct 1 ms 288 KB Output is correct
51 Incorrect 1 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 3
52 Halted 0 ms 0 KB -