oj.uz

Submission #31948

# Submission time Handle Problem Language Result Execution time Memory
31948 2017-09-18T13:00:08 Z minhtung0404 물병 (JOI14_bottle) C++14
30 / 100
 873 ms 96568 KB 
#include<bits/stdc++.h>
const int N = 2e5 + 5;
const int inf = 1e9;
using namespace std;

typedef pair <int, int> ii;
typedef pair <int, ii> iii;

vector <ii> adj[N];
priority_queue <iii, vector <iii>, greater <iii> > pq;

int n, m, p, q, x[N], y[N], dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}, lev[N], d[20][N], M[20][N];
string s[2005];
int dd[2005][2005], ee[2005][2005];

struct {
    int pset[N];
    void init(int n) {for (int i = 1; i <= n; i++) pset[i] = i;}
    int findset(int i) {return ((pset[i] == i) ? i : pset[i] = findset(pset[i]));}
    void unionset(int i, int j){
        if (findset(i) == findset(j)) return ;
        pset[findset(i)] = findset(j);
    }
} dsu;

void bfs(){
    queue <ii> mq;
    for (int i = 1; i <= p; i++){
        mq.push(ii(x[i], y[i]));
        dd[x[i]][y[i]] = 1; ee[x[i]][y[i]] = i;
    }
    while (mq.size()){
        int xx = mq.front().first, yy = mq.front().second; mq.pop();
        for (int i = 0; i < 4; i++){
            int xxx = xx + dx[i], yyy = yy + dy[i];
            if (xxx <= 0 || xxx > n || yyy <= 0 || yyy > m) continue;
            if (s[xxx][yyy] == '#') continue;
            if (dd[xxx][yyy]){
                if (ee[xx][yy] != ee[xxx][yyy]) pq.push(iii(dd[xx][yy]+dd[xxx][yyy]-2, ii(ee[xxx][yyy], ee[xx][yy])));
                continue;
            }
            dd[xxx][yyy] = dd[xx][yy] + 1; ee[xxx][yyy] = ee[xx][yy];
            mq.push(ii(xxx, yyy));
        }
    }
}

void dfs(int u, int p){
    for (int i = 0; i < adj[u].size(); i++){
        int v = adj[u][i].first, cost = adj[u][i].second;
        if (v == p) continue;
        lev[v] = lev[u] + 1;
        d[0][v] = u; M[0][v] = cost;
        dfs(v, u);
    }
}

int lca(int u, int v){
    int ans = 0;
    for (int i = 19; i >= 0; i--) if (lev[d[i][u]] >= lev[v]) ans = max(ans, M[i][u]), u = d[i][u];
    for (int i = 19; i >= 0; i--) if (lev[d[i][v]] >= lev[u]) ans = max(ans, M[i][v]), v = d[i][v];
    for (int i = 19; i >= 0; i--) {
        if (d[i][u] != d[i][v]){
            ans = max(ans, M[i][u]); ans = max(ans, M[i][v]);
            u = d[i][u]; v = d[i][v];
        }
    }
    if (u != v) ans = max(ans, M[0][u]), ans = max(ans, M[0][v]);
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> p >> q;
    for (int i = 1; i <= n; i++) {cin >> s[i]; s[i] = '.' + s[i];}
    for (int i = 1; i <= p; i++) cin >> x[i] >> y[i]; bfs();
    dsu.init(p);
    while (pq.size()){
        int cost = pq.top().first, u = pq.top().second.first, v = pq.top().second.second; pq.pop();
        if (dsu.findset(u) != dsu.findset(v)) {
            adj[u].push_back(ii(v, cost));
            adj[v].push_back(ii(u, cost));
            dsu.unionset(u, v);
        }
    }
    for (int i = 2; i <= p; i++){
        if (dsu.findset(1) != dsu.findset(i)){
            adj[1].push_back(ii(i, inf));
            adj[i].push_back(ii(1, inf));
            dsu.unionset(1, i);
        }
    }
    dfs(1, 1);
    for (int i = 1; i < 20; i++) for (int j = 1; j <= p; j++) {
        d[i][j] = d[i-1][d[i-1][j]];
        M[i][j] = max(M[i-1][j], M[i-1][d[i-1][j]]);
    }
    while (q--){
        int a, b;
        cin >> a >> b;
        int ans = lca(a, b);
        cout << ((ans == inf) ? -1 : ans) << "\n";
    }
}

Compilation message

bottle.cpp: In function 'void dfs(int, int)':
bottle.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adj[u].size(); i++){
                       ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72864 KB Output is correct
2 Correct 3 ms 72872 KB Output is correct
3 Correct 6 ms 72852 KB Output is correct
4 Runtime error 0 ms 72848 KB Execution killed because of forbidden syscall writev (20)
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 73616 KB Output is correct
2 Correct 39 ms 75668 KB Output is correct
3 Correct 436 ms 78144 KB Output is correct
4 Correct 636 ms 82016 KB Output is correct
5 Correct 736 ms 86972 KB Output is correct
6 Correct 369 ms 78152 KB Output is correct
7 Correct 593 ms 82000 KB Output is correct
8 Correct 723 ms 86980 KB Output is correct
9 Correct 873 ms 96568 KB Output is correct
10 Correct 506 ms 79260 KB Output is correct
11 Correct 626 ms 81756 KB Output is correct
12 Correct 176 ms 81752 KB Output is correct
13 Correct 193 ms 77964 KB Output is correct
14 Correct 143 ms 81752 KB Output is correct
15 Correct 186 ms 77964 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 73616 KB Output is correct
2 Correct 23 ms 73820 KB Output is correct
3 Runtime error 256 ms 76940 KB Execution killed because of forbidden syscall writev (20)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 423 ms 78300 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -