oj.uz

Submission #39540

# Submission time Handle Problem Language Result Execution time Memory
39540 2018-01-16T10:05:19 Z WhipppedCream Park (BOI16_park) C++14
100 / 100
 1073 ms 58332 KB 
#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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 58332 KB Output is correct
2 Correct 926 ms 58332 KB Output is correct
3 Correct 956 ms 58332 KB Output is correct
4 Correct 943 ms 58332 KB Output is correct
5 Correct 963 ms 58332 KB Output is correct
6 Correct 906 ms 58332 KB Output is correct
7 Correct 593 ms 58332 KB Output is correct
8 Correct 603 ms 58332 KB Output is correct
9 Correct 0 ms 33672 KB Output is correct
10 Correct 0 ms 33672 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 34140 KB Output is correct
2 Correct 53 ms 34140 KB Output is correct
3 Correct 69 ms 34140 KB Output is correct
4 Correct 53 ms 34140 KB Output is correct
5 Correct 59 ms 34140 KB Output is correct
6 Correct 66 ms 34140 KB Output is correct
7 Correct 53 ms 33672 KB Output is correct
8 Correct 46 ms 33672 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 58332 KB Output is correct
2 Correct 926 ms 58332 KB Output is correct
3 Correct 956 ms 58332 KB Output is correct
4 Correct 943 ms 58332 KB Output is correct
5 Correct 963 ms 58332 KB Output is correct
6 Correct 906 ms 58332 KB Output is correct
7 Correct 593 ms 58332 KB Output is correct
8 Correct 603 ms 58332 KB Output is correct
9 Correct 0 ms 33672 KB Output is correct
10 Correct 0 ms 33672 KB Output is correct
11 Correct 73 ms 34140 KB Output is correct
12 Correct 53 ms 34140 KB Output is correct
13 Correct 69 ms 34140 KB Output is correct
14 Correct 53 ms 34140 KB Output is correct
15 Correct 59 ms 34140 KB Output is correct
16 Correct 66 ms 34140 KB Output is correct
17 Correct 53 ms 33672 KB Output is correct
18 Correct 46 ms 33672 KB Output is correct
19 Correct 933 ms 58332 KB Output is correct
20 Correct 1073 ms 58332 KB Output is correct
21 Correct 989 ms 58332 KB Output is correct
22 Correct 886 ms 58332 KB Output is correct
23 Correct 986 ms 58332 KB Output is correct
24 Correct 736 ms 58332 KB Output is correct