oj.uz

답안 #1099960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1099960 2024-10-12T09:17:22 Z InvMOD Park (BOI16_park) C++14
100 / 100
 217 ms 29640 KB 
#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 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, (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";
                }
            }
        }
        */

        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;
}

Compilation message

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
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 28104 KB Output is correct
2 Correct 172 ms 29384 KB Output is correct
3 Correct 174 ms 28616 KB Output is correct
4 Correct 175 ms 28872 KB Output is correct
5 Correct 172 ms 28360 KB Output is correct
6 Correct 170 ms 28872 KB Output is correct
7 Correct 158 ms 27592 KB Output is correct
8 Correct 159 ms 28360 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 4760 KB Output is correct
2 Correct 30 ms 4932 KB Output is correct
3 Correct 30 ms 4692 KB Output is correct
4 Correct 30 ms 4956 KB Output is correct
5 Correct 33 ms 4948 KB Output is correct
6 Correct 32 ms 4948 KB Output is correct
7 Correct 26 ms 4444 KB Output is correct
8 Correct 27 ms 4504 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 28104 KB Output is correct
2 Correct 172 ms 29384 KB Output is correct
3 Correct 174 ms 28616 KB Output is correct
4 Correct 175 ms 28872 KB Output is correct
5 Correct 172 ms 28360 KB Output is correct
6 Correct 170 ms 28872 KB Output is correct
7 Correct 158 ms 27592 KB Output is correct
8 Correct 159 ms 28360 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 37 ms 4760 KB Output is correct
12 Correct 30 ms 4932 KB Output is correct
13 Correct 30 ms 4692 KB Output is correct
14 Correct 30 ms 4956 KB Output is correct
15 Correct 33 ms 4948 KB Output is correct
16 Correct 32 ms 4948 KB Output is correct
17 Correct 26 ms 4444 KB Output is correct
18 Correct 27 ms 4504 KB Output is correct
19 Correct 217 ms 29384 KB Output is correct
20 Correct 207 ms 28760 KB Output is correct
21 Correct 208 ms 28360 KB Output is correct
22 Correct 206 ms 29128 KB Output is correct
23 Correct 208 ms 28076 KB Output is correct
24 Correct 195 ms 29640 KB Output is correct