oj.uz

Submission #374635

# Submission time Handle Problem Language Result Execution time Memory
374635 2021-03-07T17:29:05 Z gratus907 None (KOI17_civilization) C++17
0 / 100
 1000 ms 322076 KB 
#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;
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]));
    }
    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;
    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.front();
        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;
        }
    }
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1116 ms 322076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1116 ms 322076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1116 ms 322076 KB Time limit exceeded
2 Halted 0 ms 0 KB -