Submission #443496

#	Time	Username	Problem	Language	Result	Execution time	Memory
443496		urd05	Fountain Parks (IOI21_parks)	C++17	15 / 100	3560 ms	131916 KiB

parks

#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];
bool ckk[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) {
    vector<int> uu;
    vector<int> vv;
    vector<int> aa;
    vector<int> bb;
    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]==2&&x[edge[i].second]==2) {
            uu.push_back(edge[i].first);
            vv.push_back(edge[i].second);
            aa.push_back(1);
            bb.push_back((y[edge[i].first]+y[edge[i].second])/2);
            chk[i]=true;
            ckk[i]=true;
        }
        else if (x[edge[i].first]==6&&x[edge[i].second]==6) {
            uu.push_back(edge[i].first);
            vv.push_back(edge[i].second);
            aa.push_back(7);
            bb.push_back((y[edge[i].first]+y[edge[i].second])/2);
            chk[i]=true;
            ckk[i]=true;
        }
        else if (y[edge[i].first]==y[edge[i].second]) {
            int pind1=-1;
            int pind2=-1;
            if (pt.find(P(x[edge[i].first],y[edge[i].first]-2))!=pt.end()) {
                pind1=pt[P(x[edge[i].first],y[edge[i].first]-2)];
            }
            if (pt.find(P(x[edge[i].second],y[edge[i].second]-2))!=pt.end()) {
                pind2=pt[P(x[edge[i].second],y[edge[i].second]-2)];
            }
            if (pind1!=-1&&pind2!=-1) {
                chk[i]=true;
                ckk[i]=true;
            }
        }
    }
    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()) {
                bool flag=false;
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                if (!flag) {
                    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()) {
                bool flag=false;
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                if (!flag) {
                    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()) {
                bool flag=false;
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                if (!flag) {
                    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()) {
                bool flag=false;
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                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)])];
                    if (!ckk[eind]) {
                    adj[eind].push_back(i);
                    adj[i].push_back(eind);
                    mp[P(i,eind)]=P(nx,ny);
                    mp[P(eind,i)]=P(nx,ny);
                    flag=true;
                    }
                }
                if (!flag) {
                    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];
            }
        }
    }
    for(int i=0;i<m;i++) {
            if (ckk[i]) {
                continue;
            }
        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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30