oj.uz

Submission #739667

# Submission time Handle Problem Language Result Execution time Memory
739667 2023-05-11T00:59:36 Z n0sk1ll Park (BOI16_park) C++17
100 / 100
 870 ms 70464 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const int N=2023;
int up[N+3];

int Up(int x)
{
    if (up[x]<0) return x;
    return up[x]=Up(up[x]);
}

void dsu(int a, int b)
{
    a=Up(a),b=Up(b);
    if (a==b) return;
    if (up[a]<up[b]) swap(a,b);
    up[b]+=up[a],up[a]=b;
}

bool spojeni(int a, int b)
{
    return Up(a)==Up(b);
}

int x[N+3],y[N+3],r[N+3];

ld dist(int a, int b, int c, int d)
{
    return sqrt((ld)(c-a)*(c-a)+(ld)(d-b)*(d-b));
}

string ans[100005];

bool unutar(int a, int b, int c)
{
    return a<c && c<=b;
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    int w,h; cin>>w>>h;
    ff(i,0,n) cin>>x[i]>>y[i]>>r[i];

    vector<pair<ld,pii>> dists;
    ff(i,0,n) ff(j,i+1,n) dists.pb({dist(x[i],y[i],x[j],y[j])-r[i]-r[j],{i,j}});
    ff(i,0,n)
    {
        dists.pb({y[i]-r[i],{i,n}});
        dists.pb({w-x[i]-r[i],{i,n+1}});
        dists.pb({h-y[i]-r[i],{i,n+2}});
        dists.pb({x[i]-r[i],{i,n+3}});
    }
    sort(all(dists),greater<pair<int,pii>>());

    vector<pair<pii,int>> ljudi;
    ff(i,0,m)
    {
        int tr,ty;
        cin>>tr>>ty;
        ljudi.pb({{tr,ty},i});
    }
    sort(all(ljudi));

    ff(i,0,n+4) up[i]=-1;
    //n   - dole
    //n+1 - desno
    //n+2 - gore
    //n+3 - levo

    for (auto lj : ljudi)
    {
        int tr=lj.xx.xx,ty=lj.xx.yy,ind=lj.yy;
        while (!dists.empty() && dists.back().xx<2*tr)
        {
            //cout<<"spajam "<<dists.back().yy.xx<<" i "<<dists.back().yy.yy<<endl;
            dsu(dists.back().yy.xx,dists.back().yy.yy),dists.popb();
        }

        vector<bool> blok(4,false);

        ff(i,0,4) ff(j,i+1,4) ff(dest,0,4)
        {
            if (unutar(i,j,dest)^unutar(i,j,ty-1))
                if (spojeni(n+i,n+j))
                    blok[dest]=true;
        }

        ff(i,0,4) if (!blok[i]) ans[ind].pb('1'+i);
        //cout<<"answerujem "<<ind<<" sa "<<ans[ind]<<endl;
    }

    ff(i,0,m) cout<<ans[i]<<"\n";
}

//Note to self: Check for overflow

/*

1 4
7 7
4 4 2
1 1
1 2
1 3
1 4

*/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 69396 KB Output is correct
2 Correct 814 ms 69268 KB Output is correct
3 Correct 812 ms 69324 KB Output is correct
4 Correct 814 ms 69264 KB Output is correct
5 Correct 807 ms 69380 KB Output is correct
6 Correct 819 ms 69396 KB Output is correct
7 Correct 787 ms 69236 KB Output is correct
8 Correct 798 ms 69396 KB Output is correct
9 Correct 2 ms 3464 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7352 KB Output is correct
2 Correct 51 ms 7496 KB Output is correct
3 Correct 51 ms 7360 KB Output is correct
4 Correct 55 ms 7348 KB Output is correct
5 Correct 53 ms 7388 KB Output is correct
6 Correct 53 ms 7488 KB Output is correct
7 Correct 48 ms 6268 KB Output is correct
8 Correct 51 ms 6224 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 69396 KB Output is correct
2 Correct 814 ms 69268 KB Output is correct
3 Correct 812 ms 69324 KB Output is correct
4 Correct 814 ms 69264 KB Output is correct
5 Correct 807 ms 69380 KB Output is correct
6 Correct 819 ms 69396 KB Output is correct
7 Correct 787 ms 69236 KB Output is correct
8 Correct 798 ms 69396 KB Output is correct
9 Correct 2 ms 3464 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 51 ms 7352 KB Output is correct
12 Correct 51 ms 7496 KB Output is correct
13 Correct 51 ms 7360 KB Output is correct
14 Correct 55 ms 7348 KB Output is correct
15 Correct 53 ms 7388 KB Output is correct
16 Correct 53 ms 7488 KB Output is correct
17 Correct 48 ms 6268 KB Output is correct
18 Correct 51 ms 6224 KB Output is correct
19 Correct 867 ms 70400 KB Output is correct
20 Correct 870 ms 70404 KB Output is correct
21 Correct 849 ms 70464 KB Output is correct
22 Correct 860 ms 70320 KB Output is correct
23 Correct 844 ms 70400 KB Output is correct
24 Correct 824 ms 70448 KB Output is correct