oj.uz

Submission #1104704

# Submission time Handle Problem Language Result Execution time Memory
1104704 2024-10-24T09:06:10 Z LTTrungCHL Park (BOI16_park) C++17
100 / 100
 490 ms 87332 KB 
///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
vector <int> lg2;
//void MAKE_LOG_ARR(int n){
//    lg2.resize(n + 3);
//    for (int i = 1;i <= n;++i){
//        lg2[i] = __lg(i);
//    }
//}
const long long oo = 1e9+7;
const int N = 2 * 1e5 + 10;
int n, m, w, h;
long double x[N], y[N], r[N];
int parent[N], sz[N];
vector <int> vans[N];
vector <pair <long double, pair <int ,int>>> edge, query;
long double dis(int a, int b){
    long double d = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);
    d = sqrt(d);
    return  d - r[a] - r[b];
}
void checkbien(int u){
    edge.pb({y[u] - r[u], {u, n + 1}});
    edge.pb({h - y[u] - r[u], {u, n + 3}});
    edge.pb({x[u] - r[u], {u, n + 4}});
    edge.pb({w - x[u] - r[u], {u, n + 2}});
    return;
}
int finds(int u){
    if (u == parent[u]) return u;
    int pu = finds(parent[u]);
    parent[u] = pu;
    return pu;
}
void unions(int u, int v){
    u = finds(u);
    v = finds(v);
    if (u != v){
        if (sz[u] < sz[v]) swap(u,v);
        sz[u] += sz[v];
        parent[v] = u;
    }
    return;
}
bool check(int x, int y){
    return finds(x) != finds(y);
}
bool noi(int x, int y){
    if (x == y) return true;
    if (x > y) swap(x,y);
    if (x == 1 and y == 2){
        if (check(n + 1,n + 2) and check(n + 1,n + 3) and check(n + 4, n + 1)){
            return true;
        }
    }
    if (x == 1 and y == 3){
        if (check(n + 3, n + 2) and check(n + 3, n + 1) and check(n + 4, n + 1) and check(n + 2, n + 4)){
            return true;
        }
    }
    if (x == 1 and y == 4){
        if (check(n + 4,n + 1) and check(n + 2, n + 4) and check(n + 3, n+ 4)){
            return true;
        }
    }
    if (x == 2 and y == 3){
        if (check(n + 1, n + 2) and check(n + 2, n + 4) and check(n + 2,n + 3)){
            return true;
        }
    }
    if (x == 2 and y == 4){
        if (check(n + 1, n + 3) and check(n + 2, n + 1) and check(n + 3, n + 4) and check(n + 4,n + 2)){
            return true;
        }
    }
    if (x == 3 and y == 4){
        if (check(n + 1, n+ 3) and check(n + 3,n + 2) and check(n + 3, n + 4)){
            return true;
        }
    }
    return false;
}
void solve(){
    cin >> n >> m;
    cin >> w >> h;
    for (int i = 1;i <= n;++i){
        cin >> x[i] >> y[i] >> r[i];
        checkbien(i);
    }
    for (int i = 1;i <= m;++i){
        int r, e;
        cin >> r >> e;
        query.pb({r,{e,i}});
    }
    for (int i = 1;i <= n;++i){
        for (int j = i + 1;j <= n;++j){
            edge.pb({dis(i,j), {i,j}});
        }
    }
    for (int i = 1;i <= n + 4;++i){
        parent[i] = i;
        sz[i] = 1;
    }
    sort(edge.begin(), edge.end());
    sort(query.begin(), query.end());
    int pt = 0;

//    for (int i = 0;i < query.size();++i){
//        cout << query[i].F  << " " << query[i].S.F <<" "<< query[i].S.S <<"\n";
//    }
//    cout <<"\n";
//    for (int i = 0;i < edge.size();++i){
//        cout << edge[i].F  << " " << edge[i].S.F <<" "<< edge[i].S.S <<"\n";
//    }
    for (int i = 0;i < query.size();++i){
        long double r = query[i].F;
        int e = query[i].S.F;
        int id = query[i].S.S;
        while (pt < edge.size() and edge[pt].F < r * 2){
            int u = edge[pt].S.F;
            int v = edge[pt].S.S;
            unions(u,v);
//            cout <<"NOI "<< u <<" "<< v <<"\n";
            ++pt;
        }
        vans[id].clear();
        for (int j = 1;j <= 4;++j){
            if (noi(e,j)) vans[id].pb(j);
        }
    }
    for (int i = 1;i <= m;++i){
        sort(vans[i].begin(), vans[i].end());
        for(int j : vans[i]){
            cout << j;
        }
        cout <<"\n";
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("ltt.inp", "r")){
        freopen("ltt.inp", "r", stdin);
        freopen("ltt.out", "w", stdout);
    }
//    int t;
//    cin >> t;
//    while(t--){
    solve();
//    }
    return 0;
}

Compilation message

park.cpp: In function 'void solve()':
park.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i = 0;i < query.size();++i){
      |                    ~~^~~~~~~~~~~~~~
park.cpp:129:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         while (pt < edge.size() and edge[pt].F < r * 2){
      |                ~~~^~~~~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:155:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         freopen("ltt.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
park.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen("ltt.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 78692 KB Output is correct
2 Correct 452 ms 78716 KB Output is correct
3 Correct 451 ms 78768 KB Output is correct
4 Correct 450 ms 78728 KB Output is correct
5 Correct 437 ms 78728 KB Output is correct
6 Correct 446 ms 78660 KB Output is correct
7 Correct 400 ms 78740 KB Output is correct
8 Correct 410 ms 78752 KB Output is correct
9 Correct 3 ms 10832 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 20024 KB Output is correct
2 Correct 63 ms 20040 KB Output is correct
3 Correct 72 ms 19992 KB Output is correct
4 Correct 70 ms 20180 KB Output is correct
5 Correct 71 ms 20060 KB Output is correct
6 Correct 77 ms 19804 KB Output is correct
7 Correct 57 ms 19388 KB Output is correct
8 Correct 62 ms 19388 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 78692 KB Output is correct
2 Correct 452 ms 78716 KB Output is correct
3 Correct 451 ms 78768 KB Output is correct
4 Correct 450 ms 78728 KB Output is correct
5 Correct 437 ms 78728 KB Output is correct
6 Correct 446 ms 78660 KB Output is correct
7 Correct 400 ms 78740 KB Output is correct
8 Correct 410 ms 78752 KB Output is correct
9 Correct 3 ms 10832 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 82 ms 20024 KB Output is correct
12 Correct 63 ms 20040 KB Output is correct
13 Correct 72 ms 19992 KB Output is correct
14 Correct 70 ms 20180 KB Output is correct
15 Correct 71 ms 20060 KB Output is correct
16 Correct 77 ms 19804 KB Output is correct
17 Correct 57 ms 19388 KB Output is correct
18 Correct 62 ms 19388 KB Output is correct
19 Correct 490 ms 87216 KB Output is correct
20 Correct 480 ms 87240 KB Output is correct
21 Correct 471 ms 87244 KB Output is correct
22 Correct 472 ms 87320 KB Output is correct
23 Correct 470 ms 87332 KB Output is correct
24 Correct 451 ms 86188 KB Output is correct