제출 #1099963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099963		InvMOD	Park (BOI16_park)	C++14	0 / 100	64 ms	28100 KiB

park

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

#define fi first
#define se second
#define gcd __gcd
#define vsz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 1e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


struct Circle{
    int x,y,r;
    Circle(int x = 0, int y = 0, int r = 0): x(x), y(y), r(r) {}
};
struct Edge{
    int u,v,w;
    Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
    bool operator < (const Edge& q) const{
        return w < q.w;
    }
};
struct Query{
    int id, entrance, r;
    Query(int id = 0, int entrance = 0, int r = 0): id(id), entrance(entrance), r(r) {}
    bool operator < (const Query &q) const{
        return r < q.r;
    }
};
struct DSU{
    vector<int> par,sz;
    DSU(int n = 0): par(n+1), sz(n+1) {
        for(int i = 1; i <= n; i++){
            par[i] = i;
            sz[i] = 1;
        }
        return;
    }

    int asc(int x){
        return x == par[x] ? x : par[x] = asc(par[x]);
    }

    bool join(int u, int v){
        u = asc(u), v = asc(v);
        if(u == v) return false;
        if(sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return true;
    }

    bool in(int u, int v){
        return asc(u) == asc(v);
    }
};

int n, q, h, w, answer[N];
vector<Edge> E;

Circle a[N]; Query Q[N];

ll square(int x){
    return (1ll * x * x);
}

int calc_dist(Circle a, Circle b){
    return 1ll * square(a.x - b.x) + 1ll * square(a.y - b.y) + square(a.r + b.r) - 2 * sqrt(1ll * square(a.x - b.x) + 1ll * square(a.y - b.y)) * (a.r + b.r);
}

int f(int x){
    return n+x;
}

void solve()
{
    cin >> n >> q >> w >> h;

    for(int i = 1; i <= n; i++){
        int x,y,r; cin >> x >> y >> r;
        a[i] = Circle(x, y, r);
    }

    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            E.push_back(Edge(i, j, calc_dist(a[i], a[j])));
        }
    }

    for(int i = 1; i <= q; i++){
        int entrance,r; cin >> r >> entrance;
        Q[i] = Query(i, entrance, square((r<<1)));
    }

    for(int i = 1; i <= n; i++){
        E.push_back(Edge(i, f(1), calc_dist(a[i], Circle(0, a[i].y))));
        E.push_back(Edge(i, f(2), calc_dist(a[i], Circle(a[i].x, h))));
        E.push_back(Edge(i, f(3), calc_dist(a[i], Circle(w, a[i].y))));
        E.push_back(Edge(i, f(4), calc_dist(a[i], Circle(a[i].x, 0))));
    }

    sort(all(E));
    sort(Q+1, Q+1+q);

    DSU dsu(f(4));

    int curE = 0;
    for(int i = 1; i <= q; i++){
        while(curE < E.size() && E[curE].w < Q[i].r){
            int u = E[curE].u, v = E[curE].v;
            dsu.join(u, v);
            curE = curE + 1;
        }

        /*
        for(int x = 1; x <= 4; x++){
            for(int y = x+1; y <= 4; y++){
                if(dsu.in(f(x), f(y))){
                    cout << x <<" " << y <<"\n";
                }
            }
        } cout <<"\n";
        */

        int id = Q[i].id, cur_en = Q[i].entrance;

        //check bit = 1 if can't visit that entrance
        int check = 0;

        if(cur_en == 1){
            //Check die
            if(dsu.in(f(1), f(4))){
                for(int j = 1; j <= 4; j++){
                    if(cur_en != j){
                        check = check | (1<<j);
                    }
                }
            }
            else{
                //Check horizontal
                if(dsu.in(f(1), f(3))){
                    check = check | (1<<3);
                    check = check | (1<<4);
                }
                //Check vertical
                if(dsu.in(f(2), f(4))){
                    check = check | (1<<3);
                    check = check | (1<<2);
                }

                //Check virtual
                if(dsu.in(f(1), f(2))){
                    check = check | (1<<4);
                }
                if(dsu.in(f(4), f(3))){
                    check = check | (1<<2);
                }
                if(dsu.in(f(3), f(2))){
                    check = check | (1<<3);
                }
            }
        }
        else if(cur_en == 2){
            //Check die
            if(dsu.in(f(3), f(4))){
                for(int j = 1; j <= 4; j++){
                    if(cur_en != j){
                        check = check | (1<<j);
                    }
                }
            }
            else{
                //Check horizontal
                if(dsu.in(f(1), f(3))){
                    check = check | (1<<3);
                    check = check | (1<<4);
                }
                //Check vertical
                if(dsu.in(f(2), f(4))){
                    check = check | (1<<1);
                    check = check | (1<<4);
                }

                //Check virtual
                if(dsu.in(f(1), f(4))){
                    check = check | (1<<1);
                }
                if(dsu.in(f(1), f(2))){
                    check = check | (1<<4);
                }
                if(dsu.in(f(3), f(2))){
                    check = check | (1<<3);
                }
            }
        }
        else if(cur_en == 3){
            //Check die
            if(dsu.in(f(2), f(3))){
                for(int j = 1; j <= 4; j++){
                    if(cur_en != j){
                        check = check | (1<<j);
                    }
                }
            }
            else{
                //Check horizontal
                if(dsu.in(f(1), f(3))){
                    check = check | (1<<1);
                    check = check | (1<<2);
                }
                //Check vertical
                if(dsu.in(f(2), f(4))){
                    check = check | (1<<1);
                    check = check | (1<<4);
                }

                //Check virtual
                if(dsu.in(f(1), f(4))){
                    check = check | (1<<1);
                }
                if(dsu.in(f(4), f(3))){
                    check = check | (1<<2);
                }
                if(dsu.in(f(1), f(2))){
                    check = check | (1<<4);
                }
            }
        }
        else if(cur_en == 4){
            //Check die
            if(dsu.in(f(1), f(2))){
                for(int j = 1; j <= 4; j++){
                    if(cur_en != j){
                        check = check | (1<<j);
                    }
                }
            }
            else{
                //Check horizontal
                if(dsu.in(f(1), f(3))){
                    check = check | (1<<1);
                    check = check | (1<<2);
                }
                //Check vertical
                if(dsu.in(f(2), f(4))){
                    check = check | (1<<3);
                    check = check | (1<<2);
                }

                //Check virtual
                if(dsu.in(f(1), f(4))){
                    check = check | (1<<1);
                }
                if(dsu.in(f(4), f(3))){
                    check = check | (1<<2);
                }
                if(dsu.in(f(3), f(2))){
                    check = check | (1<<3);
                }
            }
        }
        answer[id] = check;
    }

    for(int i = 1; i <= q; i++){
        for(int j = 1; j <= 4; j++){
            if(answer[i]>>j&1) continue;
            else{
                cout << j;
            }
        } cout <<"\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'void solve()':
park.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         while(curE < E.size() && E[curE].w < Q[i].r){
      |               ~~~~~^~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:298:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  298 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
park.cpp:299:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  299 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42