oj.uz

Submission #722186

# Submission time Handle Problem Language Result Execution time Memory
722186 2023-04-11T14:07:30 Z urosk Fountain Parks (IOI21_parks) C++17
25 / 100
 1250 ms 83888 KB 
#include "parks.h"
#define here cerr<<"==============================\n"
#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
using namespace std;
#define maxn 200005
ll n;
pll a[maxn];
map<pll,ll> mp;
map<pll,ll> id;
vector<ll> dx = {0,0,-2,2};
vector<ll> dy = {-2,2,0,0};
ll sz[maxn];
ll dsu[maxn];
ll col[maxn];
ll dsu2[maxn];
ll root2(ll x){
    while(x!=dsu2[x]){
        dsu2[x] = dsu2[dsu2[x]];
        x = dsu2[x];
    }
    return x;
}
bool con(ll x,ll y){return root2(x)==root2(y);}
ll tsz = 1;
bool ok = 1;
ll root(ll x){
    while(x!=dsu[x]){
        x = dsu[x];
    }
    return x;
}
void upd2(ll i,ll j){
    i = root2(i);
    j = root2(j);
    dsu2[j] = dsu2[i];
}
ll getcol(ll x){
    ll ans = col[x];
    while(x!=dsu[x]){
        x = dsu[x];
        ans^=col[x];
    }
    return ans;
}
void upd(ll i,ll j,ll e){
    e^=getcol(i)^getcol(j);
    i = root(i);
    j = root(j);
    if(i==j){
        if(e) ok = 0;
        return;
    }
    if(sz[j]>sz[i]) swap(i,j);
    sz[i]+=sz[j];
    dsu[j] = i;
    col[j]^=e;
}
int construct_roads(vector<int> X, vector<int> Y) {
    n = X.size();
    for(ll i = 1;i<=n;i++) a[i] = {X[i-1],Y[i-1]};
    for(ll i = 1;i<=n;i++) mp[a[i]] = i;
    iota(dsu+1,dsu+1+n,1);
    iota(dsu2+1,dsu2+1+n,1);
    fill(sz+1,sz+1+n,1);
    vector<ll> c,d;
    for(ll i = 1;i<=n;i++){
        ll x = a[i].fi,y = a[i].sc;
        vector<ll> v;
        for(ll e = 0;e<=3;e++){
            ll nx = x + dx[e];
            ll ny = y + dy[e];
            ll j = mp[{nx,ny}];
            v.pb(j);
            if(j&&!id[{i,j}]&&!con(i,j)){
                c.pb(i);
                d.pb(j);
                upd2(i,j);
                id[{i,j}] = id[{j,i}] = ++tsz;
            }
        }
        if(v[1]&&v[3]) upd(id[{i,v[1]}],id[{i,v[3]}],1);
        if(v[0]&&v[2]) upd(id[{i,v[0]}],id[{i,v[2]}],1);
        if(v[1]&&v[2]) upd(id[{i,v[1]}],id[{i,v[2]}],0);
        if(v[0]&&v[3]) upd(id[{i,v[0]}],id[{i,v[3]}],0);
    }
    if(!ok) return 0;
    if(c.size()<n-1) return 0;
    vector<pll> ans;
    for(ll i = 0;i<n-1;i++){
        ll x = c[i];
        ll y = d[i];
        ll j = id[{x,y}];
        ll f = getcol(j);
        if(a[x].fi==a[y].fi){
            if(f) ans.pb({a[x].fi+1,(a[x].sc+a[y].sc)/2});
            else ans.pb({a[x].fi-1,(a[x].sc+a[y].sc)/2});
        }else{
            if(f) ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc+1});
            else ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc-1});
        }
    }
    vector<ll> ansx,ansy;
    for(pll p : ans){
        ansx.pb(p.fi);
        ansy.pb(p.sc);
    }
    for(ll i = 0;i<n-1;i++){
        c[i]--;
        d[i]--;
    }
    build(c,d,ansx,ansy);
    return 1;
}
/**
5
4 4
4 6
6 4
4 2
2 4
**/

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:92:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |     if(c.size()<n-1) return 0;
      |        ~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 450 ms 41072 KB Output is correct
10 Correct 25 ms 4448 KB Output is correct
11 Correct 142 ms 22212 KB Output is correct
12 Correct 32 ms 6612 KB Output is correct
13 Correct 89 ms 15968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 448 ms 41020 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 450 ms 41072 KB Output is correct
10 Correct 25 ms 4448 KB Output is correct
11 Correct 142 ms 22212 KB Output is correct
12 Correct 32 ms 6612 KB Output is correct
13 Correct 89 ms 15968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 448 ms 41020 KB Output is correct
17 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 450 ms 41072 KB Output is correct
10 Correct 25 ms 4448 KB Output is correct
11 Correct 142 ms 22212 KB Output is correct
12 Correct 32 ms 6612 KB Output is correct
13 Correct 89 ms 15968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 448 ms 41020 KB Output is correct
17 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 450 ms 41072 KB Output is correct
10 Correct 25 ms 4448 KB Output is correct
11 Correct 142 ms 22212 KB Output is correct
12 Correct 32 ms 6612 KB Output is correct
13 Correct 89 ms 15968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 448 ms 41020 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 220 KB Output is correct
20 Correct 1189 ms 70216 KB Output is correct
21 Correct 1202 ms 70092 KB Output is correct
22 Correct 1250 ms 70044 KB Output is correct
23 Correct 889 ms 68912 KB Output is correct
24 Correct 762 ms 44912 KB Output is correct
25 Correct 1047 ms 58968 KB Output is correct
26 Correct 1000 ms 59032 KB Output is correct
27 Correct 1113 ms 69768 KB Output is correct
28 Correct 1117 ms 69748 KB Output is correct
29 Correct 1194 ms 69824 KB Output is correct
30 Correct 1169 ms 69968 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 48 ms 5608 KB Output is correct
33 Correct 186 ms 22624 KB Output is correct
34 Correct 1006 ms 70148 KB Output is correct
35 Correct 26 ms 3028 KB Output is correct
36 Correct 167 ms 14212 KB Output is correct
37 Correct 419 ms 28172 KB Output is correct
38 Correct 357 ms 26604 KB Output is correct
39 Correct 529 ms 36464 KB Output is correct
40 Correct 772 ms 46208 KB Output is correct
41 Correct 963 ms 55756 KB Output is correct
42 Correct 1143 ms 66236 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 0 ms 212 KB Output is correct
54 Correct 5 ms 852 KB Output is correct
55 Correct 7 ms 1236 KB Output is correct
56 Correct 536 ms 37600 KB Output is correct
57 Correct 827 ms 53992 KB Output is correct
58 Correct 826 ms 54092 KB Output is correct
59 Correct 0 ms 212 KB Output is correct
60 Correct 0 ms 212 KB Output is correct
61 Correct 0 ms 212 KB Output is correct
62 Correct 1030 ms 75348 KB Output is correct
63 Correct 1046 ms 75216 KB Output is correct
64 Correct 1018 ms 74968 KB Output is correct
65 Correct 8 ms 1492 KB Output is correct
66 Correct 19 ms 2684 KB Output is correct
67 Correct 478 ms 36296 KB Output is correct
68 Correct 826 ms 53660 KB Output is correct
69 Correct 1193 ms 71892 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 450 ms 41072 KB Output is correct
10 Correct 25 ms 4448 KB Output is correct
11 Correct 142 ms 22212 KB Output is correct
12 Correct 32 ms 6612 KB Output is correct
13 Correct 89 ms 15968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 448 ms 41020 KB Output is correct
17 Correct 1018 ms 81612 KB Output is correct
18 Correct 1033 ms 83888 KB Output is correct
19 Correct 1085 ms 72316 KB Output is correct
20 Incorrect 987 ms 60188 KB Solution announced impossible, but it is possible.
21 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 450 ms 41072 KB Output is correct
10 Correct 25 ms 4448 KB Output is correct
11 Correct 142 ms 22212 KB Output is correct
12 Correct 32 ms 6612 KB Output is correct
13 Correct 89 ms 15968 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 4 ms 980 KB Output is correct
16 Correct 448 ms 41020 KB Output is correct
17 Incorrect 0 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 2
18 Halted 0 ms 0 KB -