oj.uz

Submission #443481

# Submission time Handle Problem Language Result Execution time Memory
443481 2021-07-10T15:06:38 Z urd05 Fountain Parks (IOI21_parks) C++17
0 / 100
 6 ms 9676 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 construct_roads(vector<int> x, vector<int> y) {
    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++) {
        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++) {
        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:63: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]
   63 |     for(int i=0;i<edge.size();i++) {
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Incorrect 6 ms 9676 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Incorrect 6 ms 9676 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Incorrect 6 ms 9676 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Incorrect 6 ms 9676 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Incorrect 6 ms 9676 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Incorrect 6 ms 9676 KB Given structure is not connected: There is no path between vertices 0 and 1
4 Halted 0 ms 0 KB -