oj.uz

Submission #441585

# Submission time Handle Problem Language Result Execution time Memory
441585 2021-07-05T13:15:22 Z azberjibiou Fountain Parks (IOI21_parks) C++17
5 / 100
 327 ms 50992 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 140 ms 23460 KB Output is correct
10 Correct 15 ms 7048 KB Output is correct
11 Correct 69 ms 14960 KB Output is correct
12 Correct 21 ms 7788 KB Output is correct
13 Correct 19 ms 7484 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 139 ms 23144 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 140 ms 23460 KB Output is correct
10 Correct 15 ms 7048 KB Output is correct
11 Correct 69 ms 14960 KB Output is correct
12 Correct 21 ms 7788 KB Output is correct
13 Correct 19 ms 7484 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 139 ms 23144 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Runtime error 252 ms 47336 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 140 ms 23460 KB Output is correct
10 Correct 15 ms 7048 KB Output is correct
11 Correct 69 ms 14960 KB Output is correct
12 Correct 21 ms 7788 KB Output is correct
13 Correct 19 ms 7484 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 139 ms 23144 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Runtime error 252 ms 47336 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 140 ms 23460 KB Output is correct
10 Correct 15 ms 7048 KB Output is correct
11 Correct 69 ms 14960 KB Output is correct
12 Correct 21 ms 7788 KB Output is correct
13 Correct 19 ms 7484 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 139 ms 23144 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4996 KB Output is correct
19 Correct 4 ms 4992 KB Output is correct
20 Correct 327 ms 50992 KB Output is correct
21 Correct 327 ms 43016 KB Output is correct
22 Correct 322 ms 42944 KB Output is correct
23 Runtime error 158 ms 32944 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 140 ms 23460 KB Output is correct
10 Correct 15 ms 7048 KB Output is correct
11 Correct 69 ms 14960 KB Output is correct
12 Correct 21 ms 7788 KB Output is correct
13 Correct 19 ms 7484 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 139 ms 23144 KB Output is correct
17 Runtime error 222 ms 36484 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 140 ms 23460 KB Output is correct
10 Correct 15 ms 7048 KB Output is correct
11 Correct 69 ms 14960 KB Output is correct
12 Correct 21 ms 7788 KB Output is correct
13 Correct 19 ms 7484 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 139 ms 23144 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Runtime error 252 ms 47336 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -