oj.uz

Submission #69217

# Submission time Handle Problem Language Result Execution time Memory
69217 2018-08-20T09:44:07 Z MANcity Park (BOI16_park) C++14
100 / 100
 1578 ms 52588 KB 
///GAGO_O
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n,m;
LL w,h;
LL x[2002],y[2002],rad[2002];
int parent[2002];
int sz[2002];
int make_set(int v)
{
    parent[v]=v;
    sz[v]=1;
}
int find_set(int v)
{
    if(v==parent[v])
        return v;
    return parent[v]=find_set(parent[v]);
}
void union_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
    {
        if(sz[a]<sz[b])
            swap(a,b);
        parent[b]=a;
        sz[a]+=sz[b];
    }
}
int hat(int i,int j,LL R)
{
    LL x1=x[i],y1=y[i],r1=rad[i]+R;
    LL x2=x[j],y2=y[j],r2=rad[j]+R;
    if(j>n)
        r2=0;
    if(j==(n+1))
    {
        x2=R;
        y2=y1;
    }
    if(j==(n+3))
    {
        x2=(w-R);
        y2=y1;
    }
    if(j==(n+2))
    {
        y2=(h-R);
        x2=x1;
    }
    if(j==(n+4))
    {
        y2=R;
        x2=x1;
    }
    LL dist=(LL)(x1-x2)*(x1-x2)+(LL)(y1-y2)*(y1-y2);
    LL Rsum=(LL)(r1+r2)*(r1+r2);
    if(Rsum>dist)
        return 1;
    return 0;
}
vector<pair<LL,pair<int,int> > > event;
pair<LL,pair<int,int> > query[100002];
int karagna[5][5];
void pox(int i,int j)
{
    karagna[i][j]=0;
    karagna[j][i]=0;
}
void stug()
{
    int p[5];
    for1(i,4)
        p[i]=find_set(n+i);
    if(p[1]==p[2])
    {
        pox(4,1);
        pox(4,2);
        pox(4,3);
    }
    if(p[1]==p[3])
    {
        pox(4,1);
        pox(4,2);
        pox(3,1);
        pox(3,2);
    }
    if(p[1]==p[4])
    {
        pox(1,4);
        pox(1,3);
        pox(1,2);
    }
    if(p[2]==p[3])
    {
        pox(1,3);
        pox(4,3);
        pox(2,3);
    }
    if(p[2]==p[4])
    {
        pox(1,2);
        pox(1,3);
        pox(4,3);
        pox(4,2);
    }
    if(p[3]==p[4])
    {
        pox(1,2);
        pox(4,2);
        pox(3,2);
    }
}
string ANS[100002];
int main()
{
    cin>>n>>m;
    cin>>w>>h;
    for1(i,n)
        cin>>x[i]>>y[i]>>rad[i];
    for1(i,n)
        fo(j,i+1,n+4)
        {
            LL l=0;
            LL r=1000000000;
            while(1)
            {
                if(l==r)
                    break;
                LL m=(l+r)/2;
                if(hat(i,j,m)==1)
                    r=m;
                else
                    l=(m+1);
            }
            event.push_back({l,{i,j}});
        }
    sort(event.begin(),event.end());
    for1(i,n+4)
        make_set(i);
    for1(i,m)
    {
        cin>>query[i].first>>query[i].second.first;
        query[i].second.second=i;
    }
    sort(query+1,query+m+1);
    int pos=0;
    int l=event.size();
    for1(i,4)
        for1(j,4)
            karagna[i][j]=1;
    for1(i,m)
    {
        int ENT=query[i].second.first;
        int rpos=query[i].second.second;
        while(1)
        {
            if(pos >= l)
                break;
            if(event[pos].first <= query[i].first)
            {
                int a=event[pos].second.first;
                int b=event[pos].second.second;
                union_sets(a,b);
            }
            else
                break;
            pos++;
        }
        stug();
        fo(j,1,4)
            if(karagna[ENT][j]==1)
                ANS[rpos]+=(j+'0');
    }
    for1(i,m)
        cout<<ANS[i]<<endl;
    return 0;
}
/*
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
*/

Compilation message

park.cpp: In function 'int make_set(int)':
park.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1224 ms 36636 KB Output is correct
2 Correct 1254 ms 36860 KB Output is correct
3 Correct 1304 ms 36860 KB Output is correct
4 Correct 1163 ms 36860 KB Output is correct
5 Correct 1152 ms 37000 KB Output is correct
6 Correct 1206 ms 37220 KB Output is correct
7 Correct 1175 ms 37220 KB Output is correct
8 Correct 1308 ms 37256 KB Output is correct
9 Correct 5 ms 37256 KB Output is correct
10 Correct 6 ms 37256 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 37256 KB Output is correct
2 Correct 256 ms 37256 KB Output is correct
3 Correct 322 ms 37256 KB Output is correct
4 Correct 342 ms 37256 KB Output is correct
5 Correct 325 ms 37256 KB Output is correct
6 Correct 269 ms 37256 KB Output is correct
7 Correct 261 ms 37256 KB Output is correct
8 Correct 275 ms 37256 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1224 ms 36636 KB Output is correct
2 Correct 1254 ms 36860 KB Output is correct
3 Correct 1304 ms 36860 KB Output is correct
4 Correct 1163 ms 36860 KB Output is correct
5 Correct 1152 ms 37000 KB Output is correct
6 Correct 1206 ms 37220 KB Output is correct
7 Correct 1175 ms 37220 KB Output is correct
8 Correct 1308 ms 37256 KB Output is correct
9 Correct 5 ms 37256 KB Output is correct
10 Correct 6 ms 37256 KB Output is correct
11 Correct 293 ms 37256 KB Output is correct
12 Correct 256 ms 37256 KB Output is correct
13 Correct 322 ms 37256 KB Output is correct
14 Correct 342 ms 37256 KB Output is correct
15 Correct 325 ms 37256 KB Output is correct
16 Correct 269 ms 37256 KB Output is correct
17 Correct 261 ms 37256 KB Output is correct
18 Correct 275 ms 37256 KB Output is correct
19 Correct 1406 ms 47476 KB Output is correct
20 Correct 1445 ms 48376 KB Output is correct
21 Correct 1578 ms 49568 KB Output is correct
22 Correct 1481 ms 50460 KB Output is correct
23 Correct 1550 ms 51372 KB Output is correct
24 Correct 1446 ms 52588 KB Output is correct