oj.uz

Submission #1033698

# Submission time Handle Problem Language Result Execution time Memory
1033698 2024-07-25T04:17:40 Z hotboy2703 Fountain Parks (IOI21_parks) C++17
5 / 100
 66 ms 14044 KB 
#include "parks.h"

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
struct point{
    ll x,y,id;
    point(ll x1 = 0,ll y1 = 0,ll id1 = 0):x(x1),y(y1),id(id1){}
    bool operator < (const point &p)const {
        return MP(x,y) < MP(p.x,p.y);
    }
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
    ll n = sz(x);
    vector <pll> all[7];
    vector <point> a(n);
    
    for (ll i = 0;i < n;i ++){
        a[i] = {x[i],y[i],i};
    }
    sort(a.begin(),a.end());
    for (ll i = 0;i < n;i ++){
        if (all[a[i].x].empty() || all[a[i].x].back().se + 2 != a[i].y)all[a[i].x].push_back(MP(a[i].y,a[i].y));
        else{
            all[a[i].x].back().se+=2;
        }
    }
    vector <int> U, V, A, B;
    auto add = [&](pll u,pll v, ll x,ll y){
        U.push_back((*lower_bound(a.begin(),a.end(),point(u.fi,u.se,0))).id);
        V.push_back((*lower_bound(a.begin(),a.end(),point(v.fi,v.se,0))).id);
        A.push_back(x);
        B.push_back(y);
    };
    for (auto x:all[2]){
        for (ll i = x.fi + 2;i <= x.se;i += 2){
            add(MP(2,i-2),MP(2,i),1,i-1);
        }
    }
    for (auto x:all[4]){
        static ll ptr2 = 0;
        static ll ptr6 = 0;
        vector <ll> sus2,sus6;
        while (ptr2 < sz(all[2]) && all[2][ptr2].se < x.fi)ptr2++;
        while (ptr2 < sz(all[2]) && all[2][ptr2].fi <= x.se){
            pll tmp = all[2][ptr2];
            if (tmp.fi <= x.fi && x.fi <= tmp.se){
                add(MP(4,x.fi),MP(2,x.fi),3,x.fi-1);
            }
            else if (tmp.fi <= x.se && x.se <= tmp.se){
                add(MP(4,x.se),MP(2,x.se),3,x.se+1);
            }
            else{
                sus2.push_back(tmp.fi);
            }
            ptr2++;
        }

        while (ptr6 < sz(all[6]) && all[6][ptr6].se < x.fi)ptr6++;
        while (ptr6 < sz(all[6]) && all[6][ptr6].fi <= x.se){
            pll tmp = all[6][ptr6];
            if (tmp.fi <= x.fi && x.fi <= tmp.se){
                add(MP(4,x.fi),MP(6,x.fi),5,x.fi-1);
            }
            else if (tmp.fi <= x.se && x.se <= tmp.se){
                add(MP(4,x.se),MP(6,x.se),5,x.se+1);
            }
            else{
                sus6.push_back(tmp.fi);
            }
            ptr6++;
        }
        ptr2=0,ptr6=0;
        for (ll j = x.fi + 2;j <= x.se;j += 2){
            while(ptr2 < sz(sus2) && sus2[ptr2]<j)ptr2++; 
            while(ptr6 < sz(sus6) && sus6[ptr6]<j)ptr6++; 
            bool do2,do6;
            do2 =  (ptr2 < sz(sus2) && sus2[ptr2]==j);
            do6 =  (ptr6 < sz(sus6) && sus6[ptr6]==j);
            if (do2 && do6){
                add(MP(4,j),MP(2,j),3,j-1);
                add(MP(4,j),MP(6,j),5,j+1);
                add(MP(4,j),MP(4,j-2),5,j-1);
                add(MP(4,j),MP(4,j+2),3,j+1);
                j+=2;
            }
            else if (do2){
                add(MP(4,j),MP(2,j),3,j-1);
                add(MP(4,j),MP(4,j-2),5,j-1);
            }
            else if (do6){
                add(MP(4,j),MP(6,j),5,j-1);
                add(MP(4,j),MP(4,j-2),3,j-1);
            }
        }
    } 
    for (auto x:all[6]){
        for (ll i = x.fi + 2;i <= x.se;i += 2){
            add(MP(6,i-2),MP(6,i),7,i-1);
        }
    }
    {
        vector <vector <ll > > g(n);
        for (ll i = 0;i < sz(U);i ++){
            g[U[i]].push_back(V[i]);
            g[V[i]].push_back(U[i]);
        }
        vector <bool> in(n);
        queue <ll> q;
        q.push(0);
        in[0] = 1;
        while (!q.empty()){
            ll u = q.front();
            q.pop();
            for (auto v:g[u]){
                if (!in[v]){
                    in[v] = 1;
                    q.push(v);
                }
            }
        }
        for (ll i = 0;i < n;i ++)if (!in[i])return 0;
        build(U, V, A, B);
        return 1;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 62 ms 14008 KB Output is correct
10 Correct 5 ms 1644 KB Output is correct
11 Correct 25 ms 7632 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 13 ms 5076 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 59 ms 14044 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 62 ms 14008 KB Output is correct
10 Correct 5 ms 1644 KB Output is correct
11 Correct 25 ms 7632 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 13 ms 5076 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 59 ms 14044 KB Output is correct
17 Incorrect 1 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 62 ms 14008 KB Output is correct
10 Correct 5 ms 1644 KB Output is correct
11 Correct 25 ms 7632 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 13 ms 5076 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 59 ms 14044 KB Output is correct
17 Incorrect 1 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 62 ms 14008 KB Output is correct
10 Correct 5 ms 1644 KB Output is correct
11 Correct 25 ms 7632 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 13 ms 5076 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 59 ms 14044 KB Output is correct
17 Runtime error 1 ms 348 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 62 ms 14008 KB Output is correct
10 Correct 5 ms 1644 KB Output is correct
11 Correct 25 ms 7632 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 13 ms 5076 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 59 ms 14044 KB Output is correct
17 Runtime error 66 ms 13636 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 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 62 ms 14008 KB Output is correct
10 Correct 5 ms 1644 KB Output is correct
11 Correct 25 ms 7632 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 13 ms 5076 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 59 ms 14044 KB Output is correct
17 Incorrect 1 ms 348 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -