oj.uz

Submission #658963

# Submission time Handle Problem Language Result Execution time Memory
658963 2022-11-15T16:08:48 Z victor_gao Park (BOI16_park) C++17
0 / 100
 336 ms 52976 KB 
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 2015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct dsu{
    int boss[N],sz[N];
    void init(int n){
        for (int i=0;i<=n+5;i++){
            boss[i]=i; sz[i]=1;
        }
    }
    int find(int x){
        if (boss[x]==x) return x;
        return boss[x]=find(boss[x]);
    }
    void Merge(int a,int b){
        int ra=find(a),rb=find(b);
        if (ra==rb) return;
        if (sz[ra]<sz[rb]) swap(ra,rb);
        boss[rb]=ra;
        sz[ra]+=sz[rb];
    }
}d;
/*
左側 n+1, 右側 n+2, 上面 n+3, 下面 n+4
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
int n,m,w,h,r[N],vis[6];
string ans[100015];
vector<int>g[6];
vector<pair<double,pii> >edge;
vector<pair<int,pii> >people;
pii pos[N];
double count(int i,int j){
    return sqrt(1.0*(pos[i].x-pos[j].x)*(pos[i].x-pos[j].x)+1.0*(pos[i].y-pos[j].y)*(pos[i].y-pos[j].y))-r[i]-r[j];
}
void dfs(int p){
    if (vis[p]) return;
    vis[p]=1;
    for (auto i:g[p])
        dfs(i);
}
void add_edge(int i,int j){
    g[i].push_back(j);
    g[j].push_back(i);
}
string count_ans(int start){
    for (int i=0;i<5;i++){
        vis[i]=0;
        g[i].clear();
    }
    int L=d.find(n+1),R=d.find(n+2);
    int U=d.find(n+3),D=d.find(n+4);
    if (L!=U&&L!=D&&L!=R) add_edge(1,4);
    if (R!=L&&R!=U&&R!=D) add_edge(2,3);
    if (D!=L&&D!=U&&D!=R) add_edge(1,2);
    if (U!=L&&U!=R&&U!=D) add_edge(3,4);
    if (U!=D&&L!=R){
        if (U!=L&&D!=R) add_edge(2,4);
        if (L!=D&&U!=R) add_edge(1,3);
    }
    dfs(start);
    string tans="";
    for (int i=0;i<5;i++){
        if (vis[i]) tans=tans+(char)(i+'0');
    }
    return tans;
}
signed main(){
    fast
    cin>>n>>m>>w>>h;
    for (int i=1;i<=n;i++)
        cin>>pos[i].x>>pos[i].y>>r[i];
    d.init(n);
    for (int i=1;i<=m;i++){
        int r,e; cin>>r>>e;
        people.push_back({r,{e,i}});
    }
    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            double dis=count(i,j);
            edge.push_back({dis,{i,j}});
        }
    }
    for (int i=1;i<=n;i++){
        edge.push_back({h-pos[i].y-r[i],{i,n+3}});
        edge.push_back({pos[i].x-r[i],{i,n+1}});
        edge.push_back({pos[i].y-r[i],{i,n+4}});
        edge.push_back({w-pos[i].x-r[i],{i,n+2}});
    }
    sort(people.begin(),people.end());
    sort(edge.begin(),edge.end());
    int p=0;
    for (auto i:edge){
        while (p<m&&2*people[p].x<i.x){
            int st=people[p].y.x;
            ans[people[p].y.y]=count_ans(st);
            p++;
        }
        d.Merge(i.y.x,i.y.y);
    }
    for (int i=1;i<=m;i++)
        cout<<ans[i]<<"\n";
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 52892 KB Output is correct
2 Correct 312 ms 52852 KB Output is correct
3 Correct 308 ms 52860 KB Output is correct
4 Correct 336 ms 52876 KB Output is correct
5 Correct 324 ms 52924 KB Output is correct
6 Correct 323 ms 52912 KB Output is correct
7 Correct 297 ms 52976 KB Output is correct
8 Incorrect 285 ms 52832 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7488 KB Output is correct
2 Correct 50 ms 7344 KB Output is correct
3 Correct 50 ms 7400 KB Output is correct
4 Correct 55 ms 7344 KB Output is correct
5 Correct 50 ms 7344 KB Output is correct
6 Incorrect 61 ms 7476 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 52892 KB Output is correct
2 Correct 312 ms 52852 KB Output is correct
3 Correct 308 ms 52860 KB Output is correct
4 Correct 336 ms 52876 KB Output is correct
5 Correct 324 ms 52924 KB Output is correct
6 Correct 323 ms 52912 KB Output is correct
7 Correct 297 ms 52976 KB Output is correct
8 Incorrect 285 ms 52832 KB Output isn't correct
9 Halted 0 ms 0 KB -