oj.uz

Submission #443493

# Submission time Handle Problem Language Result Execution time Memory
443493 2021-07-10T15:18:22 Z urd05 Fountain Parks (IOI21_parks) C++17
45 / 100
 3071 ms 132236 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> P;
map<P,int> pt; //점->인덱스
map<P,int> ed; //인덱스쌍->간선인덱스
set<P> vis;
vector<P> edge;
vector<int> adj[400000];
map<P,P> mp;
bool chk[400000];
P ret[400000];
 
int p[200000];
 
int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}
 
void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[a]+=p[b];
    p[b]=a;
}
 
int construct_roads(vector<int> x, vector<int> y) {
    memset(p,-1,sizeof(p));
    int n=x.size();
    for(int i=0;i<n;i++) {
        pt[P(x[i],y[i])]=i;
    }
    int m=0;
    for(int i=0;i<n;i++) {
        if (pt.find(P(x[i]-2,y[i]))!=pt.end()) {
            int ind=pt[P(x[i]-2,y[i])];
            if (ed.find(P(ind,i))!=ed.end()) {
                ed[P(i,ind)]=ed[P(ind,i)];
            }
            else {
                ed[P(i,ind)]=m++;
                edge.push_back(P(i,ind));
            }
        }
        if (pt.find(P(x[i]+2,y[i]))!=pt.end()) {
            int ind=pt[P(x[i]+2,y[i])];
            if (ed.find(P(ind,i))!=ed.end()) {
                ed[P(i,ind)]=ed[P(ind,i)];
            }
            else {
                ed[P(i,ind)]=m++;
                edge.push_back(P(i,ind));
            }
        }
        if (pt.find(P(x[i],y[i]-2))!=pt.end()) {
            int ind=pt[P(x[i],y[i]-2)];
            if (ed.find(P(ind,i))!=ed.end()) {
                ed[P(i,ind)]=ed[P(ind,i)];
            }
            else {
                ed[P(i,ind)]=m++;
                edge.push_back(P(i,ind));
            }
        }
        if (pt.find(P(x[i],y[i]+2))!=pt.end()) {
            int ind=pt[P(x[i],y[i]+2)];
            if (ed.find(P(ind,i))!=ed.end()) {
                ed[P(i,ind)]=ed[P(ind,i)];
            }
            else {
                ed[P(i,ind)]=m++;
                edge.push_back(P(i,ind));
            }
        }
    }
    for(int i=0;i<edge.size();i++) {
        merge(edge[i].first,edge[i].second);
    }
    if (-p[find(0)]!=n) {
        return 0;
    }
    for(int i=0;i<edge.size();i++) {
        if (x[edge[i].first]==x[edge[i].second]) {
            int nx=x[edge[i].first]-1;
            int ny=(y[edge[i].first]+y[edge[i].second])/2;
            if (vis.find(P(nx,ny))==vis.end()) {
                if (pt.find(P(nx-1,ny+1))!=pt.end()) {
                    int pind=pt[P(nx-1,ny+1)];
                    int eind=ed[P(pind,pt[P(nx+1,ny+1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else if (pt.find(P(nx-1,ny-1))!=pt.end()) {
                    int pind=pt[P(nx-1,ny-1)];
                    int eind=ed[P(pind,pt[P(nx+1,ny-1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else {
                    adj[i].push_back(i);
                    mp[P(i,i)]=P(nx,ny);
                }
                vis.insert(P(nx,ny));
            }
            nx=x[edge[i].first]+1;
            if (vis.find(P(nx,ny))==vis.end()) {
                if (pt.find(P(nx+1,ny+1))!=pt.end()) {
                    int pind=pt[P(nx+1,ny+1)];
                    int eind=ed[P(pind,pt[P(nx-1,ny+1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else if (pt.find(P(nx+1,ny-1))!=pt.end()) {
                    int pind=pt[P(nx+1,ny-1)];
                    int eind=ed[P(pind,pt[P(nx-1,ny-1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else {
                    adj[i].push_back(i);
                    mp[P(i,i)]=P(nx,ny);
                }
                vis.insert(P(nx,ny));
            }
        }
        else {
            int nx=(x[edge[i].first]+x[edge[i].second])/2;
            int ny=y[edge[i].first]-1;
            if (vis.find(P(nx,ny))==vis.end()) {
                if (pt.find(P(nx-1,ny-1))!=pt.end()) {
                    int pind=pt[P(nx-1,ny-1)];
                    int eind=ed[P(pind,pt[P(nx-1,ny+1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else if (pt.find(P(nx+1,ny-1))!=pt.end()) {
                    int pind=pt[P(nx+1,ny-1)];
                    int eind=ed[P(pind,pt[P(nx+1,ny+1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else {
                    adj[i].push_back(i);
                    mp[P(i,i)]=P(nx,ny);
                }
                vis.insert(P(nx,ny));
            }
            ny=y[edge[i].first]+1;
            if (vis.find(P(nx,ny))==vis.end()) {
                if (pt.find(P(nx-1,ny+1))!=pt.end()) {
                    int pind=pt[P(nx-1,ny+1)];
                    int eind=ed[P(pind,pt[P(nx-1,ny-1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else if (pt.find(P(nx+1,ny+1))!=pt.end()) {
                    int pind=pt[P(nx+1,ny+1)];
                    int eind=ed[P(pind,pt[P(nx+1,ny-1)])];
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                }
                else {
                    adj[i].push_back(i);
                    mp[P(i,i)]=P(nx,ny);
                }
                vis.insert(P(nx,ny));
            }
        }
    }
    /*for(int i=0;i<m;i++) {
        printf("%d\n",adj[i].size());
        for(int j=0;j<adj[i].size();j++) {
            printf("%d ",adj[i][j]);
        }
        printf("\n");
    }*/
    for(int i=0;i<m;i++) {
        if (chk[i]) {
            continue;
        }
        if (adj[i][0]==i||adj[i][1]==i) {
 
        }
        else {
            continue;
        }
        ret[i]=mp[P(i,i)];
        int now;
        if (adj[i][0]==i) {
            now=adj[i][1];
        }
        else {
            now=adj[i][0];
        }
      chk[i]=true;
        int prev=i;
        while (1) {
            chk[now]=true;
            if (adj[now][0]==now||adj[now][1]==now) {
                ret[now]=mp[P(now,now)];
                break;
            }
            if (adj[now][0]==prev) {
                ret[now]=mp[P(now,adj[now][1])];
                prev=now;
                now=adj[now][1];
            }
            else {
                ret[now]=mp[P(now,adj[now][0])];
                prev=now;
                now=adj[now][0];
            }
        }
    }
    for(int i=0;i<m;i++) {
        if (chk[i]) {
            continue;
        }
        ret[i]=mp[P(i,adj[i][0])];
        int prev=i;
        int now=adj[i][0];
        chk[i]=true;
        while (now!=i) {
            chk[now]=true;
            if (adj[now][0]==prev) {
                ret[now]=mp[P(now,adj[now][1])];
                prev=now;
                now=adj[now][1];
            }
            else {
                ret[now]=mp[P(now,adj[now][0])];
                prev=now;
                now=adj[now][0];
            }
        }
    }
    vector<int> uu;
    vector<int> vv;
    vector<int> aa;
    vector<int> bb;
    for(int i=0;i<m;i++) {
        uu.push_back(edge[i].first);
        vv.push_back(edge[i].second);
        aa.push_back(ret[i].first);
        bb.push_back(ret[i].second);
    }
    build(uu,vv,aa,bb);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:80: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]
   80 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~
parks.cpp:86: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]
   86 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 6 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 6 ms 10444 KB Output is correct
6 Correct 8 ms 10364 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 8 ms 10444 KB Output is correct
9 Correct 744 ms 57500 KB Output is correct
10 Correct 45 ms 15180 KB Output is correct
11 Correct 249 ms 35688 KB Output is correct
12 Correct 64 ms 17536 KB Output is correct
13 Correct 92 ms 19764 KB Output is correct
14 Correct 8 ms 10572 KB Output is correct
15 Correct 13 ms 10828 KB Output is correct
16 Correct 701 ms 57568 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 6 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 6 ms 10444 KB Output is correct
6 Correct 8 ms 10364 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 8 ms 10444 KB Output is correct
9 Correct 744 ms 57500 KB Output is correct
10 Correct 45 ms 15180 KB Output is correct
11 Correct 249 ms 35688 KB Output is correct
12 Correct 64 ms 17536 KB Output is correct
13 Correct 92 ms 19764 KB Output is correct
14 Correct 8 ms 10572 KB Output is correct
15 Correct 13 ms 10828 KB Output is correct
16 Correct 701 ms 57568 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Incorrect 12 ms 10444 KB a[2] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 6 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 6 ms 10444 KB Output is correct
6 Correct 8 ms 10364 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 8 ms 10444 KB Output is correct
9 Correct 744 ms 57500 KB Output is correct
10 Correct 45 ms 15180 KB Output is correct
11 Correct 249 ms 35688 KB Output is correct
12 Correct 64 ms 17536 KB Output is correct
13 Correct 92 ms 19764 KB Output is correct
14 Correct 8 ms 10572 KB Output is correct
15 Correct 13 ms 10828 KB Output is correct
16 Correct 701 ms 57568 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Incorrect 12 ms 10444 KB a[2] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 6 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 6 ms 10444 KB Output is correct
6 Correct 8 ms 10364 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 8 ms 10444 KB Output is correct
9 Correct 744 ms 57500 KB Output is correct
10 Correct 45 ms 15180 KB Output is correct
11 Correct 249 ms 35688 KB Output is correct
12 Correct 64 ms 17536 KB Output is correct
13 Correct 92 ms 19764 KB Output is correct
14 Correct 8 ms 10572 KB Output is correct
15 Correct 13 ms 10828 KB Output is correct
16 Correct 701 ms 57568 KB Output is correct
17 Correct 7 ms 10388 KB Output is correct
18 Correct 7 ms 10444 KB Output is correct
19 Correct 7 ms 10444 KB Output is correct
20 Correct 2480 ms 108916 KB Output is correct
21 Correct 2555 ms 108712 KB Output is correct
22 Correct 2559 ms 108624 KB Output is correct
23 Correct 1608 ms 91472 KB Output is correct
24 Correct 507 ms 26124 KB Output is correct
25 Correct 1231 ms 52608 KB Output is correct
26 Correct 1097 ms 52692 KB Output is correct
27 Correct 1845 ms 104928 KB Output is correct
28 Correct 1860 ms 104872 KB Output is correct
29 Correct 2159 ms 104852 KB Output is correct
30 Correct 2141 ms 104940 KB Output is correct
31 Correct 6 ms 10404 KB Output is correct
32 Correct 92 ms 17568 KB Output is correct
33 Correct 154 ms 18292 KB Output is correct
34 Correct 2240 ms 108864 KB Output is correct
35 Correct 33 ms 12512 KB Output is correct
36 Correct 165 ms 21020 KB Output is correct
37 Correct 459 ms 31480 KB Output is correct
38 Correct 808 ms 50616 KB Output is correct
39 Correct 1195 ms 64988 KB Output is correct
40 Correct 1685 ms 81132 KB Output is correct
41 Correct 2143 ms 95636 KB Output is correct
42 Correct 2597 ms 110168 KB Output is correct
43 Correct 6 ms 10444 KB Output is correct
44 Correct 7 ms 10452 KB Output is correct
45 Correct 7 ms 10444 KB Output is correct
46 Correct 7 ms 10444 KB Output is correct
47 Correct 6 ms 10444 KB Output is correct
48 Correct 6 ms 10444 KB Output is correct
49 Correct 7 ms 10444 KB Output is correct
50 Correct 6 ms 10444 KB Output is correct
51 Correct 7 ms 10444 KB Output is correct
52 Correct 6 ms 10444 KB Output is correct
53 Correct 8 ms 10444 KB Output is correct
54 Correct 10 ms 10828 KB Output is correct
55 Correct 12 ms 11084 KB Output is correct
56 Correct 944 ms 60508 KB Output is correct
57 Correct 1529 ms 84032 KB Output is correct
58 Correct 1606 ms 84016 KB Output is correct
59 Correct 7 ms 10444 KB Output is correct
60 Correct 8 ms 10432 KB Output is correct
61 Correct 7 ms 10444 KB Output is correct
62 Correct 1598 ms 104944 KB Output is correct
63 Correct 1615 ms 104928 KB Output is correct
64 Correct 1576 ms 104448 KB Output is correct
65 Correct 14 ms 11312 KB Output is correct
66 Correct 23 ms 12128 KB Output is correct
67 Correct 1025 ms 59968 KB Output is correct
68 Correct 1648 ms 85652 KB Output is correct
69 Correct 2304 ms 109708 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 6 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 6 ms 10444 KB Output is correct
6 Correct 8 ms 10364 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 8 ms 10444 KB Output is correct
9 Correct 744 ms 57500 KB Output is correct
10 Correct 45 ms 15180 KB Output is correct
11 Correct 249 ms 35688 KB Output is correct
12 Correct 64 ms 17536 KB Output is correct
13 Correct 92 ms 19764 KB Output is correct
14 Correct 8 ms 10572 KB Output is correct
15 Correct 13 ms 10828 KB Output is correct
16 Correct 701 ms 57568 KB Output is correct
17 Correct 1779 ms 105332 KB Output is correct
18 Correct 1838 ms 105372 KB Output is correct
19 Correct 2496 ms 108660 KB Output is correct
20 Correct 3071 ms 132236 KB Output is correct
21 Correct 2078 ms 102360 KB Output is correct
22 Correct 7 ms 10444 KB Output is correct
23 Correct 250 ms 27784 KB Output is correct
24 Correct 62 ms 15172 KB Output is correct
25 Correct 289 ms 26964 KB Output is correct
26 Correct 621 ms 38888 KB Output is correct
27 Correct 1270 ms 67992 KB Output is correct
28 Correct 1657 ms 83760 KB Output is correct
29 Correct 2079 ms 97768 KB Output is correct
30 Correct 2497 ms 111536 KB Output is correct
31 Correct 2930 ms 125728 KB Output is correct
32 Correct 2600 ms 127820 KB Output is correct
33 Correct 1574 ms 105236 KB Output is correct
34 Correct 16 ms 11560 KB Output is correct
35 Correct 26 ms 12392 KB Output is correct
36 Correct 1028 ms 64312 KB Output is correct
37 Correct 1810 ms 92592 KB Output is correct
38 Correct 2518 ms 119000 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 8 ms 10444 KB Output is correct
3 Correct 6 ms 10444 KB Output is correct
4 Correct 8 ms 10444 KB Output is correct
5 Correct 6 ms 10444 KB Output is correct
6 Correct 8 ms 10364 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 8 ms 10444 KB Output is correct
9 Correct 744 ms 57500 KB Output is correct
10 Correct 45 ms 15180 KB Output is correct
11 Correct 249 ms 35688 KB Output is correct
12 Correct 64 ms 17536 KB Output is correct
13 Correct 92 ms 19764 KB Output is correct
14 Correct 8 ms 10572 KB Output is correct
15 Correct 13 ms 10828 KB Output is correct
16 Correct 701 ms 57568 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Incorrect 12 ms 10444 KB a[2] = 0 is not an odd integer
20 Halted 0 ms 0 KB -