oj.uz

Submission #474054

# Submission time Handle Problem Language Result Execution time Memory
474054 2021-09-16T17:56:05 Z idas Park (BOI16_park) C++17
100 / 100
 1070 ms 87184 KB 
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define SZ(x) ((int)((x).size()))
#define LE(vec) vec[vec.size()-1]
#define TSTS int t; cin >> t; while(t--)solve()

const int INF = 1e9;
const long long LINF = 1e18;
const long double PI = asin(1)*2;
const int MOD = 1e9+7;

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef long long ll;
typedef long double ld;

void setIO()
{
    FAST_IO;
}

void setIO (string s)
{
    setIO();
 	freopen((s+".in").c_str(),"r",stdin);
 	freopen((s+".out").c_str(),"w",stdout);
}

const int N=5e3+10, M=5e5+10;
ll n, m, w, h, par[N];
string ans[M];
vector<pair<ll, pair<ll, ll>>> vis;

int fnd(ll u)
{
    return par[u]=par[u]==u?u:fnd(par[u]);
}

bool same(ll a, ll b)
{
    return fnd(a)==fnd(b);
}

void mrg(ll a, ll b)
{
    a=fnd(a); b=fnd(b);
    if(a==b) return;
    par[a]=b;
}

bool con[10][10];

void out(ll r, ll e, ll idx)
{
    FOR(i, 0, 6) FOR(j, 0, 6) con[i][j]=true;
    if(same(n+3, n+1)){
        con[4][1]=false; con[4][2]=false;
        con[3][1]=false; con[3][2]=false;
    }
    if(same(n, n+2)){
        con[1][3]=false; con[1][2]=false;
        con[4][2]=false; con[4][3]=false;
    }

    //1
    if(same(n+3, n+2)){
        con[1][2]=false; con[1][3]=false; con[1][4]=false;
    }
    //2
    if(same(n+1, n+2)){
        con[2][1]=false; con[2][3]=false; con[2][4]=false;
    }
    //3
    if(same(n, n+1)){
        con[3][1]=false; con[3][2]=false; con[3][4]=false;
    }
    //4
    if(same(n, n+3)){
        con[4][1]=false; con[4][2]=false; con[4][3]=false;
    }

    FOR(i, 0, 5)
    {
        FOR(j, 0, 5)
        {
            con[i][j]=(con[i][j]&&con[j][i]);
        }
    }
}

char toChr(int x)
{
    if(x==0) return '0';
    if(x==1) return '1';
    if(x==2) return '2';
    if(x==3) return '3';
    if(x==4) return '4';
    if(x==5) return '5';
    if(x==6) return '6';
    if(x==7) return '7';
    if(x==8) return '8';
    if(x==9) return '9';
}

void gtAns(int e, int idx)
{
    FOR(i, 1, 5)
    {
        if(con[e][i]) ans[idx]+=toChr(i);
    }
}

void opn()
{
    freopen("t.in", "r", stdin);
    freopen("t.out", "w", stdout);
}

int main()
{
    setIO();
    //opn();
    cin >> n >> m >> w >> h;
    vector<pair<ll, pair<ll, ll>>> in;
    FOR(i, 0, n)
    {
        par[i]=i;
        ll x, y, r;
        cin >> x >> y >> r;
        in.PB({r, {x, y}});
    }
    FOR(i, n, n+4) par[i]=i;
    FOR(i, 0, m)
    {
        ll r, e;
        cin >> r >> e;
        vis.PB({r, {e, i}});
    }

    sort(vis.begin(), vis.end());

    priority_queue<pair<ld, pair<ll, ll>>, vector<pair<ld, pair<ll, ll>>>, greater<pair<ld, pair<ll, ll>>>> pth;
    FOR(i, 0, (int)in.size())
    {
        FOR(j, i+1, (int)in.size())
        {
            ll x=in[i].S.F, y=in[i].S.S, r=in[i].F, z=in[j].S.F, ww=in[j].S.S, l=in[j].F;
            ll dist=(x-z)*(x-z)+(y-ww)*(y-ww);
            ld d=sqrt(dist);
            d-=(ld)(r+l);
            pth.push({d, {i, j}});
        }
        ll x=in[i].S.F, y=in[i].S.S, r=in[i].F;

        pth.push({(h-y-r), {i, n}});
        pth.push({(w-x-r), {i, n+1}});
        pth.push({(y-r), {i, n+2}});
        pth.push({(x-r), {i, n+3}});
    }

    for(auto it : vis){
        ll r=it.F, e=it.S.F, idx=it.S.S;
        while(!pth.empty() && pth.top().F<(ld)2*r){
            mrg(pth.top().S.F, pth.top().S.S);
            pth.pop();
        }
        out(r, e, idx);
        gtAns(e, idx);
    }

    FOR(i, 0, m)
    {
        cout << ans[i] << '\n';
    }
}

Compilation message

park.cpp: In function 'void setIO(std::string)':
park.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp: In function 'char toChr(int)':
park.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^
park.cpp: In function 'void opn()':
park.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     freopen("t.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
park.cpp:123:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |     freopen("t.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 81900 KB Output is correct
2 Correct 190 ms 81820 KB Output is correct
3 Correct 191 ms 82160 KB Output is correct
4 Correct 191 ms 81764 KB Output is correct
5 Correct 186 ms 81744 KB Output is correct
6 Correct 194 ms 81792 KB Output is correct
7 Correct 1028 ms 81764 KB Output is correct
8 Correct 187 ms 81764 KB Output is correct
9 Correct 9 ms 15948 KB Output is correct
10 Correct 9 ms 15968 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 20268 KB Output is correct
2 Correct 68 ms 21316 KB Output is correct
3 Correct 64 ms 21240 KB Output is correct
4 Correct 68 ms 21376 KB Output is correct
5 Correct 67 ms 21336 KB Output is correct
6 Correct 88 ms 21372 KB Output is correct
7 Correct 63 ms 20100 KB Output is correct
8 Correct 62 ms 20188 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 81900 KB Output is correct
2 Correct 190 ms 81820 KB Output is correct
3 Correct 191 ms 82160 KB Output is correct
4 Correct 191 ms 81764 KB Output is correct
5 Correct 186 ms 81744 KB Output is correct
6 Correct 194 ms 81792 KB Output is correct
7 Correct 1028 ms 81764 KB Output is correct
8 Correct 187 ms 81764 KB Output is correct
9 Correct 9 ms 15948 KB Output is correct
10 Correct 9 ms 15968 KB Output is correct
11 Correct 81 ms 20268 KB Output is correct
12 Correct 68 ms 21316 KB Output is correct
13 Correct 64 ms 21240 KB Output is correct
14 Correct 68 ms 21376 KB Output is correct
15 Correct 67 ms 21336 KB Output is correct
16 Correct 88 ms 21372 KB Output is correct
17 Correct 63 ms 20100 KB Output is correct
18 Correct 62 ms 20188 KB Output is correct
19 Correct 286 ms 87092 KB Output is correct
20 Correct 253 ms 87056 KB Output is correct
21 Correct 252 ms 87088 KB Output is correct
22 Correct 249 ms 87108 KB Output is correct
23 Correct 241 ms 87140 KB Output is correct
24 Correct 1070 ms 87184 KB Output is correct