Submission #1094345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094345		LGQ_A3K25	Valley (BOI19_valley)	C++17	0 / 100	260 ms	262144 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db long double
#define gcd(a, b) __gcd(a, b)
#define I first
#define II second
#define pb push_back
#define ii pair<int, int>
const int INF = 2e9;
const int N = 2e5 + 2;
const int MOD = 1e9 + 7;
int n, m, w, h, x[N], y[N], r[N], par[N], ans[N];
struct edge
{
    int u, v;
    db w;
    int t;
    bool operator < (const edge& o)
    {
        if (w < o.w) return true; else
            if (w == o.w) return t > o.t;
        return false;
    }
};
vector<edge> e;
vector<ii> g[5][5];
db dist(int i, int j)
{
    return sqrt((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i])) - r[i] - r[j];
}
int get(int x)
{
    return (par[x] == -1 ? x : par[x] = get(par[x]));
}
int32_t main()
{
#define TASKNAME ""
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    if (fopen(TASKNAME".inp", "r"))
    {
        freopen(TASKNAME".inp", "r", stdin);
        freopen(TASKNAME".out", "w", stdout);
    }
    cin >> n >> m;
    cin >> w >> h;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
        e.pb({n + 1, i, y[i] - r[i], 0});
        e.pb({n + 2, i, w - x[i] - r[i], 0});
        e.pb({n + 3, i, h - y[i] - r[i], 0});
        e.pb({n + 4, i, x[i] - r[i], 0});
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) e.pb({i, j, dist(i, j), 0});
    for (int i = 1; i <= m; i++)
    {
        int r, u; cin >> r >> u;
        r *= 2;
        e.pb({u, 0, r, i});
    }
    sort(e.begin(), e.end());
    g[1][2].pb({1, 3});
    g[1][2].pb({1, 2});
    g[1][2].pb({1, 4});
    g[1][3].pb({1, 3});
    g[1][3].pb({2, 4});
    g[1][3].pb({1, 4});
    g[1][3].pb({2, 3});
    g[1][4].pb({2, 4});
    g[1][4].pb({1, 4});
    g[1][4].pb({3, 4});
    g[2][3].pb({2, 3});
    g[2][3].pb({1, 2});
    g[2][3].pb({2, 4});
    g[2][4].pb({2, 4});
    g[2][4].pb({1, 2});
    g[2][4].pb({1, 3});
    g[2][4].pb({2, 4});
    g[3][4].pb({3, 4});
    g[3][4].pb({1, 3});
    g[3][4].pb({2, 3});
    for (int i = 1; i <= n + 4; i++) par[i] = -1;
    for (auto [u, v, w, id] : e)
        if (!id)
    {
        int tx = get(u), ty = get(v);
        if (tx != ty) par[ty] = tx;
    } else
    {
        for (int i = 1; i <= 4; i++)
            if (i == u) ans[id] = ans[id] * 10 + i; else
        {
            int ok = 1, x = i, y = u;
            if (x > y) swap(x, y);
            for (auto [c, d] : g[x][y])
            {
                int tx = get(c + n), ty = get(d + n);
                if (tx == ty) ok = 0;
            }
            if (ok) ans[id] = ans[id] * 10 + i;
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int32_t main()':
valley.cpp:51:30: warning: narrowing conversion of '(y[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   51 |         e.pb({n + 1, i, y[i] - r[i], 0});
      |                         ~~~~~^~~~~~
valley.cpp:52:34: warning: narrowing conversion of '((w - x[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   52 |         e.pb({n + 2, i, w - x[i] - r[i], 0});
      |                         ~~~~~~~~~^~~~~~
valley.cpp:53:34: warning: narrowing conversion of '((h - y[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   53 |         e.pb({n + 3, i, h - y[i] - r[i], 0});
      |                         ~~~~~~~~~^~~~~~
valley.cpp:54:30: warning: narrowing conversion of '(x[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
   54 |         e.pb({n + 4, i, x[i] - r[i], 0});
      |                         ~~~~~^~~~~~
valley.cpp:62:21: warning: narrowing conversion of 'r' from 'long long int' to 'long double' [-Wnarrowing]
   62 |         e.pb({u, 0, r, i});
      |                     ^
valley.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen(TASKNAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen(TASKNAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41