oj.uz

Submission #31950

# Submission time Handle Problem Language Result Execution time Memory
31950 2017-09-18T13:35:49 Z minhtung0404 물병 (JOI14_bottle) C++14
30 / 100
 863 ms 96380 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];
char s[2005][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 < int(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(){
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 1; i <= n; i++) scanf("%s", &s[i]);
    for (int i = 1; i <= n; i++) for (int j = n; j >= 1; j--) s[i][j] = s[i][j-1];
    for (int i = 1; i <= p; i++) scanf("%d%d", &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;
        scanf("%d %d", &a, &b);
        int ans = lca(a, b);
        ans = ((ans == inf) ? -1 : ans);
        printf("%d\n", ans);
    }
}
/*
5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4
*/

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:74:51: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[2005]' [-Wformat=]
     for (int i = 1; i <= n; i++) scanf("%s", &s[i]);
                                                   ^
bottle.cpp:73:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &p, &q);
                                      ^
bottle.cpp:74:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%s", &s[i]);
                                                    ^
bottle.cpp:76:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= p; i++) scanf("%d%d", &x[i], &y[i]); bfs();
                                                             ^
bottle.cpp:100:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
                               ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 76552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 77140 KB Output is correct
2 Correct 39 ms 79028 KB Output is correct
3 Correct 376 ms 77964 KB Output is correct
4 Correct 499 ms 81844 KB Output is correct
5 Correct 686 ms 86780 KB Output is correct
6 Correct 293 ms 77964 KB Output is correct
7 Correct 596 ms 81844 KB Output is correct
8 Correct 683 ms 86788 KB Output is correct
9 Correct 863 ms 96380 KB Output is correct
10 Correct 429 ms 79068 KB Output is correct
11 Correct 526 ms 81564 KB Output is correct
12 Correct 206 ms 81432 KB Output is correct
13 Correct 206 ms 77772 KB Output is correct
14 Correct 166 ms 81432 KB Output is correct
15 Correct 216 ms 77776 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 77144 KB Output is correct
2 Incorrect 29 ms 77176 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 616 ms 78116 KB Output isn't correct
2 Halted 0 ms 0 KB -