Submission #832859

#	Time	Username	Problem	Language	Result	Execution time	Memory
832859		Ronin13	Fountain Parks (IOI21_parks)	C++17	55 / 100	1977 ms	143660 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb empalce_back
using namespace std;

map <pair<pii, pii> , int> mp;
map <pii, bool> mark; 
map <pii, int> ind;
const int nmax = 200001;
vector <int> p(nmax);
vector <int> sz(nmax);
vector <int> u, v;
vector <int> a, b;
vector <int> x, y;
vector <bool> used(nmax);
void make_set(int v){
    p[v] = v;
    sz[v] = 1;
}
int find_set(int v){
    return p[v] == v ? v : p[v] = find_set(p[v]);
}

void union_sets(int a, int b){
    if(find_set(a) == find_set(b)) return;
    mp[{{x[a - 1], y[a - 1]}, {x[b - 1], y[b -1]}}] = u.size() + 1;
    mp[{{x[b - 1], y[b - 1]}, {x[a - 1], y[a - 1]}}] = u.size() + 1;
    u.pb(a - 1);
    v.pb(b - 1);
    a = find_set(a);
    b = find_set(b);
    if(sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}

pii mark_vertical_line(int ind){
    ind--;
    //cout << ind << ' ';
    pair <pii, pii> seg = {{x[u[ind]],y[u[ind]]}, {x[v[ind]], y[v[ind]]}};
    pii A = {seg.f.f - 1, seg.f.s / 2 + seg.s.s / 2};
    if(!mark[A]){
        mark[A] = true;
        return A;
    }
    A.f += 2;
    mark[A] = true;
    return A;
}

pii mark_horizontal_line(int ind){
    ind--;
    pair <pii, pii> seg = {{x[u[ind]],y[u[ind]]}, {x[v[ind]], y[v[ind]]}};
    pii A = {seg.f.f / 2 + seg.s.f / 2, seg.f.s - 1};
    if(!mark[A]){
        mark[A] = true;
        return A;
    }
    A.s += 2;
    mark[A] = true;
    return A;
}

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    x = X, y = Y;
    int n = x.size();
    for(int i = 0; i < n; i++){
        ind[{x[i], y[i]}] = i + 1;
    }
    for(int i= 1; i <= n; i++)
        make_set(i);
    
    for(int i = 0; i < n; i++){
        if(ind[{x[i], y[i] - 2}])
            union_sets(ind[{x[i], y[i] - 2}], i + 1);
        if(ind[{x[i], y[i] + 2}])
            union_sets(ind[{x[i], y[i] + 2}], i + 1);
    }
    for(int i = 0; i < n; i++){
        if(ind[{x[i] + 2, y[i]}])
            union_sets(ind[{x[i] + 2, y[i]}], i + 1);
        if(ind[{x[i] - 2, y[i]}])
            union_sets(ind[{x[i] - 2, y[i]}], i + 1);
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(find_set(i) == i) cnt++;
    }
    if(cnt > 1) return 0;
    a.resize(u.size());
    b.resize(v.size());
   
    set <int> st;
    for(int i = 1; i <= u.size(); i++)
        st.insert(i);
    while(!st.empty()){
        int s = *st.begin();
        st.erase(st.begin());
      // cout << s << "\n";
        bool ind = true;
        while(s){
            used[s] = true;
            st.erase(s);
            pii B;
            if(x[u[s - 1]] == x[v[s - 1]]){
                B = mark_vertical_line(s);
                a[s - 1] = B.f, b[s -1] = B.s;
                s = 0;
            }
            else{
                B = mark_horizontal_line(s);
                a[s - 1] = B.f, b[s - 1] = B.s;
                s = 0;
            }
          //  cout << B.f << ' ' << B.s << "\n";
            pii pos[] = {{B.f - 1, B.s - 1}, {B.f + 1, B.s - 1}, {B.f - 1, B.s + 1}, {B.f + 1, B.s + 1}};
            for(int i = 0; i < 4; i++){
                for(int j = i + 1; j < 4; j++){
                    int o = mp[{pos[i], pos[j]}];
                    if(o && !used[o]){
                        s = o;
                        break;
                    }
                }
            }
        }
    }
    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:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 1; i <= u.size(); i++)
      |                    ~~^~~~~~~~~~~
parks.cpp:107:14: warning: unused variable 'ind' [-Wunused-variable]
  107 |         bool ind = true;
      |              ^~~

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