제출 #828846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828846		fatemetmhr	분수 공원 (IOI21_parks)	C++17	70 / 100	507 ms	91148 KiB

parks

// Be Name Khoda //

//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair

const int maxn5 = 1e6 + 10;


int n, q[maxn5], cnt[maxn5];
bool mark[maxn5];
vector <int> ret[2], ed[2], edg[maxn5];
vector <pair<int, int>> ver;
pair<pair <int, int>, pair<int, int>> adj[maxn5];
map <pair<int, int>, int> av;

void dfs(int v, int x, int y){
    av.erase(mp(x, y));
    if(av.find(mp(x - 2, y)) != av.end()){
        int u = av[mp(x - 2, y)];
        ed[0].pb(v);
        ed[1].pb(u);
        dfs(u, x - 2, y);
    }
    if(av.find(mp(x + 2, y)) != av.end()){
        int u = av[mp(x + 2, y)];
        ed[0].pb(v);
        ed[1].pb(u);
        dfs(u, x + 2, y);
    }
    if(av.find(mp(x, y - 2)) != av.end()){
        int u = av[mp(x, y - 2)];
        ed[0].pb(v);
        ed[1].pb(u);
        dfs(u, x, y - 2);
    }
    if(av.find(mp(x, y + 2)) != av.end()){
        int u = av[mp(x, y + 2)];
        ed[0].pb(v);
        ed[1].pb(u);
        dfs(u, x, y + 2);
    }
}

void dfs2(int v){
    mark[v] = true;
    for(auto u : edg[v]) if(!mark[u]){
        mark[u] = true;
        //debug(v);
        //debug(u);
        ret[0][v] = ver[u - (n - 1)].fi;
        ret[1][v] = ver[u - (n - 1)].se;
        for(auto z : edg[u]) if(!mark[z])
            dfs2(z);
        return;
    }
}


int construct_roads(std::vector<int> x, std::vector<int> y) {
    n = x.size();
    for(int i = 0; i < n; i++)
        av[mp(x[i], y[i])] = i;
    dfs(0, x[0], y[0]);
    if(av.size())
        return 0;

    for(int i = 0; i < n - 1; i++){
        if(x[ed[0][i]] == x[ed[1][i]]){
            adj[i].fi = mp(x[ed[0][i]] - 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
            adj[i].se = mp(x[ed[0][i]] + 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
        }
        else{
            adj[i].fi = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] - 1);
            adj[i].se = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] + 1);
        }
        ver.pb(adj[i].fi);
        ver.pb(adj[i].se);
    }

    sort(all(ver));
    ver.resize(unique(all(ver)) - ver.begin());
    for(int i = 0; i < n - 1; i++){
        int pt = lower_bound(all(ver), adj[i].fi) - ver.begin();
        edg[i].pb(pt + n - 1);
        pt = lower_bound(all(ver), adj[i].se) - ver.begin();
        edg[i].pb(pt + n - 1);
        edg[edg[i][0]].pb(i);
        edg[edg[i][1]].pb(i);
        cnt[edg[i][0]]++;
        cnt[edg[i][1]]++;
    }
    /*
    for(int i = 0; i < int(ver.size()) + n - 1; i++){
        //debug(i);
        for(auto u : edg[i])
            cout << u << ' ';
        cout << endl;
    }
    //*/
    int l = 0, r = 0;
    for(int i = 0; i < int(ver.size()); i++) if(edg[i + n - 1].size() == 1){
        q[r++] = i + n - 1;
        mark[i + n - 1] = true;
    }
    ret[0].resize(n - 1);
    ret[1].resize(n - 1);
    //debug(r);
    while(l < r){
        int v = q[l++];
        for(auto u : edg[v]) if(!mark[u]){
            mark[u] = true;
            for(auto z : edg[u]){
                cnt[z]--;
                if(!mark[z] && cnt[z] == 1){
                    q[r++] = z;
                    mark[z] = true;
                }
            }
            ret[0][u] = ver[v - (n - 1)].fi;
            ret[1][u] = ver[v - (n - 1)].se;
        }
    }
    for(int i = 0; i < int(ver.size()); i++)
        assert(cnt[i + n - 1] < 3);
    //return 0;
    //cout << ed[0].size() << ' ' << ed[1].size() << ' ' << ret[0].size() << ' ' << ret[1].size() << endl;
    for(int i = 0; i < n - 1; i++) if(!mark[i])
        dfs2(i);
    build(ed[0], ed[1], ret[0], ret[1]);
    return 1;
}

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