oj.uz

Submission #443489

# Submission time Handle Problem Language Result Execution time Memory
443489 2021-07-10T15:13:02 Z urd05 Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 105280 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];
        }
        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 7 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10416 KB Output is correct
4 Correct 8 ms 10384 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 7 ms 10444 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 667 ms 57508 KB Output is correct
10 Correct 40 ms 15172 KB Output is correct
11 Correct 232 ms 35724 KB Output is correct
12 Correct 59 ms 17476 KB Output is correct
13 Correct 89 ms 19828 KB Output is correct
14 Correct 8 ms 10624 KB Output is correct
15 Correct 11 ms 10872 KB Output is correct
16 Correct 694 ms 57756 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10416 KB Output is correct
4 Correct 8 ms 10384 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 7 ms 10444 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 667 ms 57508 KB Output is correct
10 Correct 40 ms 15172 KB Output is correct
11 Correct 232 ms 35724 KB Output is correct
12 Correct 59 ms 17476 KB Output is correct
13 Correct 89 ms 19828 KB Output is correct
14 Correct 8 ms 10624 KB Output is correct
15 Correct 11 ms 10872 KB Output is correct
16 Correct 694 ms 57756 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Execution timed out 3556 ms 10460 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10416 KB Output is correct
4 Correct 8 ms 10384 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 7 ms 10444 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 667 ms 57508 KB Output is correct
10 Correct 40 ms 15172 KB Output is correct
11 Correct 232 ms 35724 KB Output is correct
12 Correct 59 ms 17476 KB Output is correct
13 Correct 89 ms 19828 KB Output is correct
14 Correct 8 ms 10624 KB Output is correct
15 Correct 11 ms 10872 KB Output is correct
16 Correct 694 ms 57756 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Execution timed out 3556 ms 10460 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10416 KB Output is correct
4 Correct 8 ms 10384 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 7 ms 10444 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 667 ms 57508 KB Output is correct
10 Correct 40 ms 15172 KB Output is correct
11 Correct 232 ms 35724 KB Output is correct
12 Correct 59 ms 17476 KB Output is correct
13 Correct 89 ms 19828 KB Output is correct
14 Correct 8 ms 10624 KB Output is correct
15 Correct 11 ms 10872 KB Output is correct
16 Correct 694 ms 57756 KB Output is correct
17 Correct 7 ms 10444 KB Output is correct
18 Incorrect 7 ms 10444 KB Tree @(199999, 199999) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10416 KB Output is correct
4 Correct 8 ms 10384 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 7 ms 10444 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 667 ms 57508 KB Output is correct
10 Correct 40 ms 15172 KB Output is correct
11 Correct 232 ms 35724 KB Output is correct
12 Correct 59 ms 17476 KB Output is correct
13 Correct 89 ms 19828 KB Output is correct
14 Correct 8 ms 10624 KB Output is correct
15 Correct 11 ms 10872 KB Output is correct
16 Correct 694 ms 57756 KB Output is correct
17 Incorrect 1703 ms 105280 KB Tree @(3, 100001) appears more than once: for edges on positions 80415 and 80416
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10444 KB Output is correct
2 Correct 6 ms 10444 KB Output is correct
3 Correct 7 ms 10416 KB Output is correct
4 Correct 8 ms 10384 KB Output is correct
5 Correct 7 ms 10444 KB Output is correct
6 Correct 7 ms 10444 KB Output is correct
7 Correct 8 ms 10444 KB Output is correct
8 Correct 6 ms 10444 KB Output is correct
9 Correct 667 ms 57508 KB Output is correct
10 Correct 40 ms 15172 KB Output is correct
11 Correct 232 ms 35724 KB Output is correct
12 Correct 59 ms 17476 KB Output is correct
13 Correct 89 ms 19828 KB Output is correct
14 Correct 8 ms 10624 KB Output is correct
15 Correct 11 ms 10872 KB Output is correct
16 Correct 694 ms 57756 KB Output is correct
17 Correct 6 ms 10444 KB Output is correct
18 Correct 6 ms 10444 KB Output is correct
19 Execution timed out 3556 ms 10460 KB Time limit exceeded
20 Halted 0 ms 0 KB -