답안 #31947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31947 2017-09-18T12:57:40 Z minhtung0404 물병 (JOI14_bottle) C++14
0 / 100
6 ms 524288 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(){
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = 1; i <= n; i++) {scanf("%s", &s[i]); s[i] = '.' + s[i];}
    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);
        printf("%d\n", ((ans == inf) ? -1 : ans));
    }
}

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++){
                       ^
bottle.cpp: In function 'int main()':
bottle.cpp:74:52: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'std::__cxx11::string* {aka std::__cxx11::basic_string<char>*}' [-Wformat=]
     for (int i = 1; i <= n; i++) {scanf("%s", &s[i]); s[i] = '.' + 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:53: 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]); s[i] = '.' + s[i];}
                                                     ^
bottle.cpp:75: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:99:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
                              ^
# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 6 ms 524288 KB Memory limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 0 ms 524288 KB Memory limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 3 ms 524288 KB Memory limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 3 ms 524288 KB Memory limit exceeded
2 Halted 0 ms 0 KB -