Submission #617833

#	Time	Username	Problem	Language	Result	Execution time	Memory
617833		happypotato	Fountain Parks (IOI21_parks)	C++17	30 / 100	864 ms	77732 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
const int mxN = 2e5 + 1;
const int dx[mxN] = {0, 1, 0, -1}, dy[mxN] = {1, 0, -1, 0};
bool vis[mxN];
pair<pii, int> pts[mxN];
pii opts[mxN];
map<pii, int> allpts;
int n;
vector<pii> edges;
vector<pii> imp;
bool CheckConnected() {
    queue<pii> q;
    set<pii> track;
    q.push(pts[0].ff);
    track.insert(pts[0].ff);
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = cur.ff + dx[k] * 2;
            int ny = cur.ss + dy[k] * 2;
            if (allpts.find({nx, ny}) != allpts.end() && track.find({nx, ny}) == track.end()) {
                q.push({nx, ny});
                track.insert({nx, ny});
                edges.pb({allpts[cur], allpts[{nx, ny}]});
            }
        }
    }
    return (int(track.size()) == n);
}
void st123() {
    int arr[3][mxN + 10];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < mxN + 10; j++) {
            arr[i][j] = -1;
        }
    }
    for (int i = 0; i < n; i++) {
        arr[(pts[i].ff.ff >> 1) - 1][pts[i].ff.ss] = pts[i].ss;
    }
    bool con01 = false, con12 = false;
    bool notfix = false;
    vector<int> u, v, a, b;
    for (int i = 0; i < mxN + 6; i += 2) {
        // if (i <= 10) cout << arr[0][i] << ' ' << arr[1][i] << ' ' << arr[2][i] << endl;
        if (arr[0][i] >= 0 && arr[0][i + 2] >= 0) {
            u.pb(arr[0][i]); v.pb(arr[0][i + 2]);
            a.pb(1); b.pb(i + 1);
        }
        if (arr[2][i] >= 0 && arr[2][i + 2] >= 0) {
            u.pb(arr[2][i]); v.pb(arr[2][i + 2]);
            a.pb(7); b.pb(i + 1);
        }
        bool special = false;
        if (notfix) {
            u.pb(arr[0][i]); v.pb(arr[1][i]);
            a.pb(3); b.pb(i + 1);
            special = true;
            notfix = false;
        }
        bool usemid = false;
        if (!(arr[1][i + 2] >= 0 && arr[2][i + 2] >= 0 && !con12)) special = true;
        if (arr[1][i] >= 0 && arr[1][i + 2] >= 0) {
            u.pb(arr[1][i]); v.pb(arr[1][i + 2]);
            a.pb((special ? 5 : 3)); b.pb(i + 1);
            usemid = !special;
        }
        if (arr[0][i + 2] >= 0 && arr[1][i + 2] >= 0 && !con01) {
            if (!usemid) {
                u.pb(arr[0][i + 2]); v.pb(arr[1][i + 2]);
                a.pb(3); b.pb(i + 1);
            } else notfix = true;
            con01 = true;
        } else con01 = false;
        if (arr[1][i + 2] >= 0 && arr[2][i + 2] >= 0 && !con12) {
            u.pb(arr[1][i + 2]); v.pb(arr[2][i + 2]);
            a.pb(5); b.pb(i + 1);
            con12 = true;
        } else con12 = false;
    }
    build(u, v, a, b);
    return;
}
void st45() {
    set<pair<pii, pii> > edgeset;
    for (pii &cur : edges) {
        pair<pii, pii> edge = {opts[cur.ff], opts[cur.ss]};
        if (edge.ff.ff > edge.ss.ff) {
            swap(edge.ff, edge.ss);
            swap(cur.ff, cur.ss);
        } else if (edge.ff.ff == edge.ss.ff && edge.ff.ss > edge.ss.ss) {
            swap(edge.ff, edge.ss);
            swap(cur.ff, cur.ss);
        }
        edgeset.insert(edge);
    }
    vector<int> ordering[4];
    for (int i = 0; i < edges.size(); i++) {
        pii fir = opts[edges[i].ff], sec = opts[edges[i].ss];
        pii important;
        bool left, right, middle;
        if (fir.ff == sec.ff) {
            // -2
            left = (edgeset.find({{fir.ff - 2, fir.ss}, fir}) != edgeset.end());
            right = (edgeset.find({{sec.ff - 2, sec.ss}, sec}) != edgeset.end());
            middle = (edgeset.find({{fir.ff - 2, fir.ss}, {sec.ff - 2, sec.ss}}) != edgeset.end());
            if (left && right) important.ff = 3;
            else if (middle) important.ff = 2;
            else if (left || right) important.ff = 1;
            else important.ff = 0;
            // +2
            left = (edgeset.find({fir, {fir.ff + 2, fir.ss}}) != edgeset.end());
            right = (edgeset.find({sec, {sec.ff + 2, sec.ss}}) != edgeset.end());
            middle = (edgeset.find({{fir.ff + 2, fir.ss}, {sec.ff + 2, sec.ss}}) != edgeset.end());
            if (left && right) important.ss = 3;
            else if (middle) important.ss = 2;
            else if (left || right) important.ss = 1;
            else important.ss = 0;
        } else if (fir.ss == sec.ss) {
            // -2
            left = (edgeset.find({{fir.ff, fir.ss - 2}, fir}) != edgeset.end());
            right = (edgeset.find({{sec.ff, sec.ss - 2}, sec}) != edgeset.end());
            middle = (edgeset.find({{fir.ff, fir.ss - 2}, {sec.ff, sec.ss - 2}}) != edgeset.end());
            if (left && right) important.ff = 3;
            else if (middle) important.ff = 2;
            else if (left || right) important.ff = 1;
            else important.ff = 0;
            // +2
            left = (edgeset.find({fir, {fir.ff, fir.ss + 2}}) != edgeset.end());
            right = (edgeset.find({sec, {sec.ff, sec.ss + 2}}) != edgeset.end());
            middle = (edgeset.find({{fir.ff, fir.ss + 2}, {sec.ff, sec.ss + 2}}) != edgeset.end());
            if (left && right) important.ss = 3;
            else if (middle) important.ss = 2;
            else if (left || right) important.ss = 1;
            else important.ss = 0;
        }
        imp.pb(important);
        ordering[max(important.ff, important.ss)].pb(i);
    }
    int m = edges.size();
    vector<pii> coor(m);
    set<pii> appear;
    for (int urgency = 3; urgency >= 0; urgency--) {
        for (int &cur : ordering[urgency]) {
            pii fir = opts[edges[cur].ff], sec = opts[edges[cur].ss];
            if (imp[cur].ff >= imp[cur].ss && appear.find({fir.ff + 1, fir.ss + 1}) == appear.end()) {
                // add
                coor[cur] = {fir.ff + 1, fir.ss + 1};
            } else if (appear.find({sec.ff - 1, sec.ss - 1}) == appear.end()) {
                // minus
                coor[cur] = {sec.ff - 1, sec.ss - 1};
            } else throw runtime_error("");
            appear.insert(coor[cur]);
        }
    }
    vector<int> u(m), v(m), a(m), b(m);
    for (int i = 0; i < m; i++) {
        u[i] = edges[i].ff;
        v[i] = edges[i].ss;
        a[i] = coor[i].ff;
        b[i] = coor[i].ss;
    }
    build(u, v, a, b);
    return;
}
int construct_roads(vector<int> ox, vector<int> oy) {
    n = ox.size();
    int maxx = 0;
    for (int i = 0; i < n; i++) {
        pts[i] = {{ox[i], oy[i]}, i};
        opts[i] = pts[i].ff;
        allpts[pts[i].ff] = i;
        maxx = max(maxx, pts[i].ff.ff);
    }
    // for (int i = 0; i < n; i++) {
    //     cout << pts[i].ff.ff << ' ' << pts[i].ff.ss << ' ' << pts[i].ss << endl;
    // }
    if (!CheckConnected()) return 0;
    if (maxx <= 6) st123();
    else st45();
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'void st45()':
parks.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int i = 0; i < edges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

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