oj.uz

답안 #68955

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68955 2018-08-19T11:04:50 Z Vahan Park (BOI16_park) C++17
0 / 100
 2500 ms 65984 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,m,k[6][6],u[3000],w,h,x[4000],y[4000],r[4000];
vector<pair<double,long long> > g[4000];
void stug(long long a,long long b)
{
    if(a==n+1)
    {
        if(b==n+2)
        {
            k[4][3]=1;
            k[4][2]=1;
            k[4][1]=1;
        }
        if(b==n+3)
        {
            k[4][1]=1;
            k[4][2]=1;
            k[3][1]=1;
            k[3][2]=1;
        }
        if(b==n+4)
        {
            k[1][4]=1;
            k[1][3]=1;
            k[1][2]=1;
        }
    }
    if(a==n+2)
    {
        if(b==n+3)
        {
            k[3][1]=1;
            k[3][2]=1;
            k[3][4]=1;
        }
        if(b==n+4)
        {
            k[3][1]=1;
            k[3][4]=1;
            k[2][1]=1;
            k[2][4]=1;
        }
    }
    if(a==n+3)
    {
        if(b==n+4)
        {
            k[2][1]=1;
            k[2][3]=1;
            k[2][4]=1;
        }
    }
}
double dis(long long a,long long b)
{
    return (double)sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))-r[a]-r[b];
}
void dfs(long long v,long long a,long long q)
{
    u[v]=1;
    if(v>q)
        stug(q,v);
    for(long long i=0;i<g[v].size();i++)
    {
        long long to=g[v][i].second;
        double her=g[v][i].first;
        if(her>(double)a)
            break;
        if(u[to]==0)
            dfs(to,a,q);
    }
}
int main()
{
    cin>>n>>m;
    cin>>w>>h;
    for(long long i=1;i<=n;i++)
        cin>>x[i]>>y[i]>>r[i];
    for(long long i=1;i<n;i++)
    {
        for(long long j=i+1;j<=n;j++)
        {
            double e=dis(i,j);
            g[i].push_back({e,j});
            g[j].push_back({e,i});
        }
    }
    for(long long i=1;i<=n;i++)
    {
        g[n+1].push_back({x[i]-r[i],i});
        g[n+2].push_back({h-y[i]-r[i],i});
        g[n+3].push_back({w-x[i]-r[i],i});
        g[n+4].push_back({y[i]-r[i],i});
        g[i].push_back({x[i]-r[i],n+1});
        g[i].push_back({h-y[i]-r[i],n+2});
        g[i].push_back({w-x[i]-r[i],n+3});
        g[i].push_back({y[i]-r[i],n+4});
    }
    for(long long i=1;i<=n+4;i++)
        sort(g[i].begin(),g[i].end());
    for(long long i=1;i<=m;i++)
    {
        long long a,an;
        cin>>a>>an;
        a*=2;
        dfs(n+1,a,n+1);
        for(long long j=1;j<=n+4;j++)
            u[j]=0;
        dfs(n+2,a,n+2);
        for(long long j=1;j<=n+4;j++)
            u[j]=0;
        dfs(n+3,a,n+3);
        for(long long j=1;j<=n+4;j++)
            u[j]=0;
        for(long long j=1;j<=4;j++)
        {
            if(k[an][j]==0 && k[j][an]==0)
                cout<<j;
        }
        for(long long j=1;j<=4;j++)
        {
            for(long long e=1;e<=4;e++)
                k[j][e]=0;
        }
        cout<<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 'void dfs(long long int, long long int, long long int)':
park.cpp:67:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i=0;i<g[v].size();i++)
                       ~^~~~~~~~~~~~

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 65320 KB Output is correct
2 Correct 530 ms 65340 KB Output is correct
3 Correct 555 ms 65340 KB Output is correct
4 Correct 506 ms 65592 KB Output is correct
5 Correct 560 ms 65592 KB Output is correct
6 Correct 556 ms 65792 KB Output is correct
7 Correct 499 ms 65984 KB Output is correct
8 Incorrect 508 ms 65984 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 555 ms 65984 KB Output is correct
2 Correct 814 ms 65984 KB Output is correct
3 Correct 822 ms 65984 KB Output is correct
4 Correct 851 ms 65984 KB Output is correct
5 Correct 525 ms 65984 KB Output is correct
6 Execution timed out 2552 ms 65984 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 557 ms 65320 KB Output is correct
2 Correct 530 ms 65340 KB Output is correct
3 Correct 555 ms 65340 KB Output is correct
4 Correct 506 ms 65592 KB Output is correct
5 Correct 560 ms 65592 KB Output is correct
6 Correct 556 ms 65792 KB Output is correct
7 Correct 499 ms 65984 KB Output is correct
8 Incorrect 508 ms 65984 KB Output isn't correct
9 Halted 0 ms 0 KB -