oj.uz

Submission #31946

# Submission time Handle Problem Language Result Execution time Memory
31946 2017-09-18T12:31:24 Z minhtung0404 물병 (JOI14_bottle) C++14
60 / 100
 1336 ms 96456 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(){
    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 6 ms 72700 KB Output is correct
2 Correct 16 ms 72852 KB Output is correct
3 Correct 13 ms 72688 KB Output is correct
4 Runtime error 409 ms 72688 KB Execution timed out (wall clock limit exceeded)
5 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 73496 KB Output is correct
2 Correct 59 ms 75552 KB Output is correct
3 Correct 539 ms 78036 KB Output is correct
4 Correct 723 ms 81896 KB Output is correct
5 Correct 809 ms 86856 KB Output is correct
6 Correct 583 ms 78036 KB Output is correct
7 Correct 666 ms 81884 KB Output is correct
8 Correct 736 ms 86860 KB Output is correct
9 Correct 1002 ms 96452 KB Output is correct
10 Correct 516 ms 79140 KB Output is correct
11 Correct 573 ms 81640 KB Output is correct
12 Correct 306 ms 81620 KB Output is correct
13 Correct 326 ms 77848 KB Output is correct
14 Correct 283 ms 81612 KB Output is correct
15 Correct 329 ms 77848 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 73500 KB Output is correct
2 Correct 39 ms 73704 KB Output is correct
3 Correct 383 ms 76824 KB Output is correct
4 Correct 663 ms 81888 KB Output is correct
5 Correct 809 ms 86860 KB Output is correct
6 Correct 1039 ms 96456 KB Output is correct
7 Correct 613 ms 79128 KB Output is correct
8 Correct 659 ms 81912 KB Output is correct
9 Correct 353 ms 81616 KB Output is correct
10 Correct 496 ms 77844 KB Output is correct
11 Correct 413 ms 77040 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1336 ms 78184 KB Execution timed out (wall clock limit exceeded)
2 Halted 0 ms 0 KB -