oj.uz

Submission #31951

# Submission time Handle Problem Language Result Execution time Memory
31951 2017-09-18T13:38:14 Z minhtung0404 물병 (JOI14_bottle) C++14
100 / 100
 3196 ms 156400 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 = 0; i < n; i++) scanf("%s", &s[i]);
    for (int i = 1; i <= p; i++) {
        scanf("%d %d", &x[i], &y[i]);
        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);
    }
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:74:50: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[2005]' [-Wformat=]
     for (int i = 0; i < n; i++) scanf("%s", &s[i]);
                                                  ^
bottle.cpp:73:41: 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:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 0; i < n; i++) scanf("%s", &s[i]);
                                                   ^
bottle.cpp:76:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x[i], &y[i]);
                                     ^
bottle.cpp:102: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 76552 KB Output is correct
2 Correct 9 ms 76696 KB Output is correct
3 Correct 9 ms 76556 KB Output is correct
4 Correct 119 ms 76552 KB Output is correct
5 Correct 113 ms 76700 KB Output is correct
6 Correct 113 ms 76552 KB Output is correct
7 Correct 136 ms 76552 KB Output is correct
8 Correct 126 ms 76896 KB Output is correct
9 Correct 119 ms 76420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 77140 KB Output is correct
2 Correct 56 ms 79020 KB Output is correct
3 Correct 399 ms 77964 KB Output is correct
4 Correct 516 ms 81844 KB Output is correct
5 Correct 669 ms 86780 KB Output is correct
6 Correct 346 ms 77964 KB Output is correct
7 Correct 619 ms 81844 KB Output is correct
8 Correct 706 ms 86788 KB Output is correct
9 Correct 869 ms 96380 KB Output is correct
10 Correct 363 ms 79068 KB Output is correct
11 Correct 429 ms 81564 KB Output is correct
12 Correct 143 ms 81432 KB Output is correct
13 Correct 186 ms 77772 KB Output is correct
14 Correct 159 ms 81432 KB Output is correct
15 Correct 196 ms 77776 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 77144 KB Output is correct
2 Correct 26 ms 77176 KB Output is correct
3 Correct 256 ms 76752 KB Output is correct
4 Correct 489 ms 81840 KB Output is correct
5 Correct 663 ms 86784 KB Output is correct
6 Correct 809 ms 96384 KB Output is correct
7 Correct 383 ms 79056 KB Output is correct
8 Correct 483 ms 81840 KB Output is correct
9 Correct 203 ms 81564 KB Output is correct
10 Correct 219 ms 77772 KB Output is correct
11 Correct 193 ms 76992 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 78116 KB Output is correct
2 Correct 1719 ms 98592 KB Output is correct
3 Correct 366 ms 79064 KB Output is correct
4 Correct 2333 ms 118108 KB Output is correct
5 Correct 3196 ms 156400 KB Output is correct
6 Correct 923 ms 87168 KB Output is correct
7 Correct 309 ms 79072 KB Output is correct
8 Correct 116 ms 77792 KB Output is correct
9 Correct 2889 ms 156216 KB Output is correct
10 Correct 1329 ms 104332 KB Output is correct
11 Correct 2276 ms 155600 KB Output is correct
12 Correct 1746 ms 120564 KB Output is correct