Submission #39540

#	Time	Username	Problem	Language	Result	Execution time	Memory
39540		WhipppedCream	Park (BOI16_park)	C++14	100 / 100	1073 ms	58332 KiB

park

#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vvi vector< vi >
#define vii vector< ii >
#define mp make_pair
#define pb push_back
const int maxn = 2010;
int adj[maxn][maxn];
int x[maxn], y[maxn], r[maxn];
int p[maxn];
vector<int> graph[maxn];
int dist[maxn][maxn];
int res[5][5];
int findset(int k)
{
    if(k == p[k]) return k;
    return p[k] = findset(p[k]);
}
void unionset(int x, int y)
{
    int a = findset(x), b = findset(y);
    p[a] = b;
}
bool cmp(ii A, ii B)
{
    return adj[A.X][A.Y]< adj[B.X][B.Y];
}
void dfs(int u, int p, int cur, int from)
{
    dist[from][u] = cur;
    for(auto v : graph[u])
    {
        if(v == p) continue;
        dfs(v, u, max(cur, adj[u][v]), from);
    }
}
int main()
{
    //#ifndef atom
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    //#endif
    int n, m; scanf("%d %d", &n, &m);
    int w, h; scanf("%d %d", &w, &h);
    for(int i = 1; i<= n; i++)
    {
        scanf("%d %d %d", x+i, y+i, r+i);
    }
    for(int i = 1; i<= n+4; i++) p[i] = i;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= n; j++)
        {
            if(i == j) continue;
            double dist = hypot(x[i]-x[j], y[i]-y[j])-r[i]-r[j];
            adj[i][j] = (int) floor(dist/2 + 1e-10);
        }
    }
    for(int i = 1; i<= n; i++)
    {
        adj[n+1][i] = adj[i][n+1] = (y[i]-r[i])/2;
        adj[n+2][i] = adj[i][n+2] = (x[i]-r[i])/2;
        adj[n+3][i] = adj[i][n+3] = (h-y[i]-r[i])/2;
        adj[n+4][i] = adj[i][n+4] = (w-x[i]-r[i])/2;
    }
    vii edge;
    for(int i = 1; i<= n; i++)
    {
        for(int j = i+1; j<= n+4; j++)
        {
            edge.pb(ii(i, j));
        }
    }
    sort(edge.begin(), edge.end(), cmp);
    for(int i = 0; i< (int) edge.size(); i++)
    {
        int a = edge[i].X, b = edge[i].Y;
        if(findset(a) != findset(b))
        {
            unionset(a, b);
            graph[a].pb(b); graph[b].pb(a);
            //printf("edge %d %d\n", a, b);
        }
    }
    for(int i = n+1; i<= n+4; i++) dfs(i, -1, 0, i);
    for(int i = 1; i<= 4; i++) res[i][i] = 1e9;
    res[1][2] = res[2][1] = min(min(dist[n+1][n+2], dist[n+1][n+3]), dist[n+1][n+4]);
    res[1][3] = res[3][1] = min(min(min(dist[n+1][n+2], dist[n+1][n+3]), dist[n+3][n+4]), dist[n+2][n+4]);
    res[1][4] = res[4][1] = min(min(dist[n+2][n+3], dist[n+2][n+4]), dist[n+2][n+1]);
    res[2][3] = res[3][2] = min(min(dist[n+4][n+1], dist[n+4][n+2]), dist[n+4][n+3]);
    res[2][4] = res[4][2] = min(min(min(dist[n+1][n+4], dist[n+1][n+3]), dist[n+2][n+3]), dist[n+2][n+4]);
    res[3][4] = res[4][3] = min(min(dist[n+3][n+1], dist[n+3][n+2]), dist[n+3][n+4]);
    for(int i = 0; i< m; i++)
    {
        int r, e; scanf("%d %d", &r, &e);
        for(int j = 1; j<= 4; j++)
        {
            if(res[e][j]>= r) printf("%d", j);
        }
        printf("\n");
    }

}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:49:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, m; scanf("%d %d", &n, &m);
                                     ^
park.cpp:50:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int w, h; scanf("%d %d", &w, &h);
                                     ^
park.cpp:53:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", x+i, y+i, r+i);
                                         ^
park.cpp:101:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int r, e; scanf("%d %d", &r, &e);
                                         ^

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42