Submission #441585

#	Time	Username	Problem	Language	Result	Execution time	Memory
441585		azberjibiou	Fountain Parks (IOI21_parks)	C++17	5 / 100	327 ms	50992 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define pii pair<int, int>
const int mxN=200020;
typedef struct pnt{
    int fir, sec, idx;
}pnt;
typedef struct edge{
    int nxt, p1, p2;
}edge;
int N;
vector <pii> coor;
vector <edge> adj[mxN];
pnt A[mxN];
int par[mxN];
bool Chk[mxN];
vector <int> u, v, a, b;
bool cmp1(pnt a, pnt b)
{
    if(a.fir!=b.fir)    return a.fir<b.fir;
    return a.sec<b.sec;
}
bool cmp2(pnt a, pnt b)
{
    if(a.sec!=b.sec)    return a.sec<b.sec;
    return a.fir<b.fir;
}
int findpar(int a)
{
    return (par[a]==a ? a : par[a]=findpar(par[a]));
}
void onion(int a, int b)
{
    int p=findpar(a), q=findpar(b);
    if(p!=q)    par[p]=q;
}
void dfs1(int now, int pre)
{
    Chk[now]=true;
    for(auto ele : adj[now])  if(ele.nxt!=pre)
    {
        u.push_back(ele.p1);   v.push_back(ele.p2);
        a.push_back(coor[ele.nxt].fir); b.push_back(coor[ele.nxt].sec);
        dfs1(ele.nxt, now);
    }
}
void dfs2(int now, int pre, int s)
{
    //printf("now=%d\n", now);
    Chk[now]=true;
    for(auto ele : adj[now])    if(ele.nxt!=pre)
    {
        u.push_back(ele.p1);   v.push_back(ele.p2);
        a.push_back(coor[now].fir); b.push_back(coor[now].sec);
        if(ele.nxt==s)  return;
        dfs2(ele.nxt, now, s);
        if(now==s)  return;
    }
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    N=x.size();
    for(int i=0;i<N;i++)    A[i].fir=x[i], A[i].sec=y[i], A[i].idx=i;
    for(int i=0;i<N;i++)    par[i]=i;
    sort(A, A+N, cmp1);
    for(int i=1;i<N;i++)
    {
        if(A[i-1].fir==A[i].fir && A[i-1].sec==A[i].sec-2)
        {
            onion(A[i-1].idx, A[i].idx);
            coor.push_back({A[i].fir+1, A[i].sec-1});
            coor.push_back({A[i].fir-1, A[i].sec-1});
        }
    }
    sort(A, A+N, cmp2);
    for(int i=1;i<N;i++)
    {
        if(A[i-1].sec==A[i].sec && A[i-1].fir==A[i].fir-2)
        {
            onion(A[i-1].idx, A[i].idx);
            coor.push_back({A[i].fir-1, A[i].sec-1});
            coor.push_back({A[i].fir-1, A[i].sec+1});
        }
    }
    for(int i=1;i<N;i++)    if(findpar(i)!=findpar(i-1))    return 0;
    sort(coor.begin(), coor.end());
    coor.erase(unique(coor.begin(), coor.end()), coor.end());
    sort(A, A+N, cmp1);
    for(int i=1;i<N;i++)
    {
        if(A[i-1].fir==A[i].fir && A[i-1].sec==A[i].sec-2)
        {
            pii tmp1={A[i].fir+1, A[i].sec-1}, tmp2={A[i].fir-1, A[i].sec-1};
            int t1=lower_bound(coor.begin(), coor.end(), tmp1)-coor.begin();
            int t2=lower_bound(coor.begin(), coor.end(), tmp2)-coor.begin();
            adj[t1].push_back({t2, A[i-1].idx, A[i].idx});
            adj[t2].push_back({t1, A[i-1].idx, A[i].idx});
        }
    }
    sort(A, A+N, cmp2);
    for(int i=1;i<N;i++)
    {
        if(A[i-1].sec==A[i].sec && A[i-1].fir==A[i].fir-2)
        {
            pii tmp1={A[i].fir-1, A[i].sec-1}, tmp2={A[i].fir-1, A[i].sec+1};
            int t1=lower_bound(coor.begin(), coor.end(), tmp1)-coor.begin();
            int t2=lower_bound(coor.begin(), coor.end(), tmp2)-coor.begin();
            adj[t1].push_back({t2, A[i-1].idx, A[i].idx});
            adj[t2].push_back({t1, A[i-1].idx, A[i].idx});
        }
    }
    for(int i=0;i<coor.size();i++)
    {
        if(!Chk[i] && adj[i].size()==1)
        {
            dfs1(i, -1);
        }
    }
    for(int i=0;i<coor.size();i++)
    {
        if(!Chk[i])
        {
            dfs2(i, -1, i);
        }
    }
    build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

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

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