#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
const int V = 101010;
struct DSU
{
int par[V], sz[V];
DSU(){init(V);}
void init(int n)
{
for (int i = 0; i<n; i++)
par[i] = i, sz[i] = 1;
}
int find(int x)
{
return x == par[x] ? x : (par[x] = find(par[x]));
}
int getSize(int k){return sz[find(k)];}
void unite(int x, int y)
{
int u=find(x), v=find(y);
if(u==v) return;
if(sz[u]>sz[v]) swap(u, v);
sz[v]+=sz[u];
sz[u] = 0;
par[u] = par[v];
}
} D;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
pii civID [2020][2020];
int n, k;
struct civ {
int r, c, id, year;
bool operator<(const civ &o) const
{
return year > o.year;
}
};
bool violated(int r, int c)
{
return not (1 <= r and r <= n and 1 <= c and c <= n);
}
int32_t main()
{
usecppio
cin >> n >> k;
priority_queue<civ> q;
for (int i = 1; i <= k; i++)
{
int r, c; cin >> r >> c;
q.push({r, c, i, 0});
civID[r][c] = {i, 0};
}
while(!q.empty())
{
civ cv = q.top();
int r = cv.r, c = cv.c;
//printf("CIV %lld on %lld %lld year %lld\n",cv.id, r, c, cv.year);
q.pop();
for (int i = 0; i < 4; i++)
{
int nr = r + dr[i], nc = c + dc[i];
if (violated(nr, nc))
continue;
if (civID[nr][nc].first != 0 and civID[nr][nc].second <= cv.year)
D.unite(civID[nr][nc].first, cv.id);
else
{
civID[nr][nc] = {cv.id, cv.year+1};
q.push({nr, nc, cv.id, cv.year+1});
}
}
if (D.sz[D.find(1)] == k)
{
cout << cv.year << '\n';
return 0;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
265164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
265164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
265164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
