제출 #436521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436521		dacin21	분수 공원 (IOI21_parks)	C++17	45 / 100	1144 ms	89320 KiB

parks

#include "parks.h"

#include <bits/stdc++.h>
using namespace std;

const int U = 1.01e5;

struct Segment{
    int x, y;
    bool vert;
};
struct Range{
    int a, b;
};

struct Dsu{
    Dsu(int n_) : p(n_, -1){}
    int f(int x){
        return p[x] < 0 ? x : p[x] = f(p[x]);
    }
    bool u(int a, int b){
        a = f(a);
        b = f(b);
        if(a == b) return false;
        p[b] = a;
        return true;
    }
    vector<int> p;
};
// 2-sat in linear time via backtracking.
class Two_Sat {
public:
    int N; // number of variables
    vector<int> val; // assignment of x is at val[2x] and -x at val[2x+1]
    vector<char> valid; // changes made at time i are kept iff valid[i]
    vector<vector<int> > G; // graph of implications G[x][i] = y means (x -> y)

    Two_Sat(int N_) : N(N_) { // create a formula over N variables (numbered 1 to N)
        G.resize(2*N);
    }

    int add_variable() {
        G.emplace_back();
        G.emplace_back();
        return N++;
    }

private:
    // converts a signed variable index to its position in val[] and G[]
    int to_ind(int x) {
        return 2*(abs(x)-1) + (x<0);
    }

    // Add a directed edge to the graph.
    // You most likely do not want to call this yourself!
    void add_edge(int a, int b) {
        G[to_ind(a)].push_back(to_ind(b));
    }

    int time() {
        return valid.size()-1;
    }

    bool dfs(int x) {
        if(valid[abs(val[x])]) return val[x]>0;
        val[x] = time();
        val[x^1] = -time();
        for(int e:G[x])
            if(!dfs(e))
                return false;
        return true;
    }

public:
    // Add the or-clause: (a or b)
    void add_or(int a, int b) {
        add_edge(-a,b);
        add_edge(-b,a);
    }

    // Add the implication: a -> b
    void add_implication(int a, int b) {
        add_or(-a, b);
    }

    // Add condition: x is true
    void add_true(int x) {
        add_or(x,x);
    }

    // At most one with linear number of clauses
    template<typename T>
    void add_at_most_one(T vars) {
        if(vars.begin() == vars.end()) return;
        int last = *vars.begin();
        int cur = 0;
        for(int const&e:vars){
            if(e == last) continue;
            if(cur == 0) cur = e;
            else {
                add_or(-cur, -e);
                int new_cur = add_variable();
                cur = add_implication(cur, new_cur);
                add_implication(e, new_cur);
                cur = new_cur;
            }
        }
        if(cur != 0){
            add_or(-cur, -last);
        }
    }

    bool solve() {
        val.assign(2*N, 0);
        valid.assign(1, 0);
        for(int i=0; i<(int)val.size(); i+=2) {
            if(!valid[abs(val[i])]) {
                valid.push_back(1);
                if(!dfs(i)) {
                    valid.back()=0;
                    valid.push_back(1);
                    if(!dfs(i+1)) return false;
                }
            }
        }
        return true;
    }
};

const int inf = 1e9;

int construct_roads(vector<int> X, vector<int> Y) {
    const int n = X.size();
    map<pair<int, int>, int> decode;
    for(int i=0; i<n; ++i){
        decode[make_pair(X[i], Y[i])] = i;
    }
    Dsu uni(n);
    vector<array<int, 4> > to(n, {-1, -1, -1, -1});
    vector<array<int, 4> > var(n, {0, 0, 0, 0});
    int vars = 0;
    for(int i=0; i<n; ++i){
        for(int j=0; j<4; ++j){
            int x = X[i], y = Y[i];
            if(j == 0) x+=2;
            if(j == 2) x-=2;
            if(j == 1) y+=2;
            if(j == 3) y-=2;
            if(decode.count(make_pair(x, y))){
                to[i][j] = decode[make_pair(x, y)];
                if(uni.u(i, to[i][j])){
                    assert(var[i][j] == 0);
                    ++vars;
                    var[i][j] = vars;
                    var[to[i][j]][j^2] = vars;
                }
                //cerr << i << " " << X[i] << " " << Y[i] << " with " << j << " -> " << x << " " << y << " " << to[i][j] << " " << var[i][j] << "\n";
            }
        }
    }
    Two_Sat sat(vars);
    auto check = [&](int a, int b){
        if(a == 0 || a == inf) return;
        if(b == 0 || b == inf) return;
        //cerr << "or " << a << " " << b << "\n";
        sat.add_or(a, b);
    };
    for(int i=0; i<n; ++i){
        check(var[i][0], var[i][1]);
        check(var[i][2], -var[i][1]);
        check(-var[i][2], -var[i][3]);
        check(-var[i][0], var[i][3]);
        if(to[i][0] != -1){
            check(-var[i][1], var[to[i][0]][1]);
        }
        if(to[i][1]!= -1){
            check(-var[i][0], var[to[i][1]][0]);
        }
    }
    assert(sat.solve());
    vector<int> out_a, out_b, out_x, out_y;
    for(int i=0; i<n; ++i){
        for(int j=0; j<2; ++j) if(var[i][j] && var[i][j] != inf){
            const int e = to[i][j];
            out_a.push_back(i);
            out_b.push_back(e);
            int x = X[i];
            int y = Y[i];
            if(j == 0) x+=1;
            if(j == 2) x-=1;
            if(j == 1) y+=1;
            if(j == 3) y-=1;
            int add;
            if(sat.val[2*var[i][j]-2]>0){
                add = -1;
            } else {
                add = 1;
            }
            if(j%2 == 0) y += add;
            else x += add;
            out_x.push_back(x);
            out_y.push_back(y);
        }
    }
    if((int)out_x.size() == n-1){
        build(out_a, out_b, out_x, out_y);
        return 1;
    }
    return 0;
}

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