Submission #754226

#	Time	Username	Problem	Language	Result	Execution time	Memory
754226		nonono	Park (BOI16_park)	C++17	0 / 100	320 ms	49688 KiB

park

#include "bits/stdc++.h"
#define int long long
using namespace std;
 
const int mxN = 2e3 + 5;
const int mxM = 1e5 + 10;
 
bool mark[1 << 5], check[mxM][5];
 
struct DSU {
    vector<int> lab, dir;
    
    void init(int n){
        lab.resize(n + 5);
        dir.resize(n + 5);
        
        for(int i = 1; i <= n; i ++){
            lab[i] = -1;
            dir[i] = 0;
        }
    }
    
    int get_root(int u){
        return lab[u] < 0 ? u : lab[u] = get_root(lab[u]);
    }
    
    bool unite(int u, int v){
        u = get_root(u);
        v = get_root(v);
        
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        
        lab[u] += lab[v];
        dir[u] |= dir[v];
        mark[dir[u]] = true;
        lab[v] = u;
        
        return true;
    }
} dsu;
 
int n, m, w, h;
array<int, 3> a[mxN], b[mxM];
 
bool f(int x, int y){
    return mark[(1 << x) + (1 << y)];
}
 
int sqr(int x){
    return x * x;
}
 
int sqrDist(int x, int y, int r, int u, int v, int R){
    return sqr(abs(x - u) - r - R) + sqr(abs(y - v) - r - R);
}
 
signed main(){
 
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> w >> h;
    dsu.init(n);
    memset(mark, false, sizeof(mark));
    
    for(int i = 1; i <= n; i ++){
        int x, y, R;
        cin >> x >> y >> R;
        
        a[i] = {x, y, R};
    }
    
    for(int i = 1; i <= m; i ++){
        int R, e;
        cin >> R >> e;
        
        b[i] = {R, e, i};
    }
    
    sort(b + 1, b + 1 + m);
    
    vector<array<int, 3>> edge;
    
    for(int i = 1; i <= n; i ++){
        int x = a[i][0];
        int y = a[i][1];
        int r = a[i][2];
        
        for(int j = i + 1; j <= n; j ++){
            int u = a[j][0];
            int v = a[j][1];
            int R = a[j][2];
            
            edge.push_back({sqrDist(x, y, r, u, v, R), i, j});            
        }
    }
    
    sort(edge.begin(), edge.end());
    
    vector<array<int, 3>> D;
    
    for(int i = 1; i <= n; i ++){
        int x, y;
        int R = a[i][2];
        
        x = w - a[i][0] + R;
        D.push_back({x, i, 2});
        
        x = a[i][0] - R;
        D.push_back({x, i, 8});
        
        y = h - a[i][1] + R;
        D.push_back({y, i, 1});
        
        y = a[i][1] - R;
        D.push_back({y, i, 4});
    }
    
    sort(D.begin(), D.end());
    
    for(int i = 1, j = 0, k = 0; i <= m; i ++){
        int R = b[i][0] * 2;
        int e = b[i][1];
        int id = b[i][2];
        
        while(j <= edge.size() && edge[j][0] <= sqr(R)){
            int u = edge[j][1];
            int v = edge[j][2];
            
            dsu.unite(u, v);
            j ++ ;
        }
        
        while(k <= D.size() && D[k][0] <= R){
            int u = dsu.get_root(D[k][1]);
            dsu.dir[u] |= D[k][2];
            mark[dsu.dir[u]] = true;
            k ++ ;
        }
        
        for(int mask = (1 << 5) - 1; mask >= 0; mask --){
            if(!mark[mask]) continue ;
            for(int _j = 0; _j < 5; _j ++){
                if(mask >> _j & 1){
                    mark[mask ^ (1 << _j)] = true;
                }
            }
        }
        
        for(int _j = 1; _j <= 4; _j ++) check[id][_j] = true;
            
        if(e == 1){
            if(f(2, 3)) check[id][2] = check[id][3] = check[id][4] = false;
            if(f(0, 2)) check[id][2] = check[id][3] = false;
            if(f(1, 3)) check[id][3] = check[id][4] = false;
            if(f(1, 2)) check[id][2] = false;
            if(f(0, 1)) check[id][3] = false;
            if(f(0, 3)) check[id][4] = false;
        }
        
        if(e == 2){
            if(f(1, 2)) check[id][1] = check[id][3] = check[id][4] = false;
            if(f(0, 2)) check[id][1] = check[id][4] = false;
            if(f(1, 3)) check[id][3] = check[id][4] = false;
            if(f(2, 3)) check[id][1] = false;
            if(f(0, 1)) check[id][3] = false;
            if(f(0, 3)) check[id][4] = false;
        }
        
        if(e == 3){
            if(f(0, 1)) check[id][1] = check[id][2] = check[id][4] = false;
            if(f(0, 2)) check[id][1] = check[id][4] = false;
            if(f(1, 3)) check[id][1] = check[id][2] = false;
            if(f(2, 3)) check[id][1] = false;
            if(f(1, 2)) check[id][2] = false;
            if(f(0, 3)) check[id][4] = false;
        }
        
        if(e == 4){
            if(f(0, 3)) check[id][1] = check[id][2] = check[id][3] = false;
            if(f(0, 2)) check[id][2] = check[id][3] = false;
            if(f(1, 3)) check[id][1] = check[id][2] = false;
            if(f(2, 3)) check[id][1] = false;
            if(f(1, 2)) check[id][2] = false;
            if(f(0, 1)) check[id][3] = false;
        }
    }
    
    for(int i = 1; i <= m; i ++){
        for(int j = 1; j <= 4; j ++){
            if(check[i][j]) cout << j;
        }
        
        cout << "\n";
    }
    
    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:126:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         while(j <= edge.size() && edge[j][0] <= sqr(R)){
      |               ~~^~~~~~~~~~~~~~
park.cpp:134:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         while(k <= D.size() && D[k][0] <= R){
      |               ~~^~~~~~~~~~~

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