Submission #1024258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024258		dpsaveslives	Park (BOI16_park)	C++17	100 / 100	218 ms	35260 KiB

park

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct DSU{
    int N;
    vector<int> d;
    void init(int n){
        N = n;
        d = vector<int>(N,-1);
    }
    int finden(int x){
        if(d[x] < 0) return x;
        return (d[x] = finden(d[x]));
    }
    bool unite(int a, int b){
        a = finden(a), b = finden(b);
        if(a == b) return false;
        if(d[a] < d[b]) swap(a,b);
        d[b] += d[a]; d[a] = b;
        return true;
    }
};
struct edge{
    int u,v; ll w;
    bool operator<(const edge &b){
        return w < b.w;
    }
};
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M; cin >> N >> M;
    int W,H; cin >> W >> H;
    vector<edge> edges;
    vector<ll> x(N+5),y(N+5),r(N+5);
    for(int i = 5;i<=N+4;++i){
        cin >> x[i] >> y[i] >> r[i]; edge e;
        e.u = 1; e.v = i; e.w = H-y[i]-r[i]; edges.push_back(e);
        e.u = 2; e.v = i; e.w = W-x[i]-r[i]; edges.push_back(e);
        e.u = 3; e.v = i; e.w = y[i]-r[i]; edges.push_back(e);
        e.u = 4; e.v = i; e.w = x[i]-r[i]; edges.push_back(e);
        for(int j = 5;j<i;++j){
            e.u = i; e.v = j; e.w = (ll)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j];
            edges.push_back(e);
        }
    }
    sort(edges.begin(),edges.end());
    DSU D; D.init(N+5);
    vector<vector<int>> res(5,vector<int>(5,-1));
    for(int i = 0;i<edges.size();++i){
        int u = edges[i].u, v = edges[i].v;
        ll w = edges[i].w;
        D.unite(u,v);
        for(int j = 1;j<=4;++j){
            for(int k = j+1;k<=4;++k){
                if(res[j][k] == -1 && D.finden(j) == D.finden(k)){
                    res[j][k] = res[k][j] = w;
                }
            }
        }
    }
    for(int i = 0;i<M;++i){
        ll rq; int en; cin >> rq >> en;
        rq *= 2;
        vector<bool> ok(5,true);
        if(en == 1){
            if(res[1][2] < rq){
                ok[3] = false;
            }
            if(res[1][3] < rq){
                ok[2] = ok[3] = false;
            }
            if(res[1][4] < rq){
                ok[4] = false;
            }
            if(res[2][3] < rq){
                ok[2] = false;
            }
            if(res[2][4] < rq){
                ok[3] = ok[4] = false;
            }
            if(res[3][4] < rq){
                ok[2] = ok[3] = ok[4] = false;
            }
        }
        else if(en == 2){
            if(res[3][4] < rq){
                ok[1] = false;
            }
            if(res[1][2] < rq){
                ok[3] = false;
            }
            if(res[1][4] < rq){
                ok[4] = false;
            }
            if(res[1][3] < rq){
                ok[1] = ok[4] = false;
            }
            if(res[2][3] < rq){
                ok[1] = ok[3] = ok[4] = false;
            }
            if(res[2][4] < rq){
                ok[3] = ok[4] = false;
            }

        }
        else if(en == 3){
            if(res[3][4] < rq){
                ok[1] = false;
            }
            if(res[2][3] < rq){
                ok[2] = false;
            }
            if(res[1][2] < rq){
                ok[1] = ok[2] = ok[4] = false;
            }
            if(res[1][4] < rq){
                ok[4] = false;
            }
            if(res[1][3] < rq){
                ok[1] = ok[4] = false;
            }
            if(res[2][4] < rq){
                ok[1] = ok[2] = false;
            }

        }
        else{
             if(res[3][4] < rq){
                ok[1] = false;
            }
            if(res[2][3] < rq){
                ok[2] = false;
            }
            if(res[1][2] < rq){
                ok[3] = false;
            }
            if(res[2][4] < rq){
                ok[1] = ok[2] = false;
            }
            if(res[1][3] < rq){
                ok[2] = ok[3] = false;
            }
            if(res[1][4] < rq){
                ok[2] = ok[3] = ok[1] = false;
            }

        }
        for(int j = 1;j<=4;++j){
            if(ok[j]) cout << j;
        }
        cout << "\n";
    }
    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0;i<edges.size();++i){
      |                   ~^~~~~~~~~~~~~

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