oj.uz

답안 #895328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895328 2023-12-29T18:55:04 Z TahirAliyev Inside information (BOI21_servers) C++17
0 / 100
 57 ms 16624 KB 
#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 12e4 + 4, LOGMAX = 18;
int n, m;
int par[LOGMAX][MAX];
int tin[MAX], tout[MAX];
int h[MAX];
vector<pii> g[MAX];
int dp[MAX][2];
int parl[MAX];

int t = 1;
void dfs(int node, int p){
    par[0][node] = p;
    tin[node] = t++;
    for(pii to : g[node]){
        if(p == to.first) continue;
        h[to.first] = h[node] + 1;
        dp[to.first][0] = node;
        dp[to.first][1] = node;
        if((parl[node] > to.second) || !parl[node]){
            dp[to.first][0] = dp[node][0];
        }
        if((parl[node] < to.second) || !parl[node]){
            dp[to.first][1] = dp[node][1];
        }
        parl[to.first] = to.second; 
        dfs(to.first, node);
    }
    tout[node] = t++;
}

bool isAnc(int u, int v){
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int lift(int u, int l){
    for(int j = LOGMAX - 1; j >= 0; j--){
        if(!isAnc(par[j][u], l)) u = par[j][u];
    }
    return u;
}
int lca(int u, int v){
    if(isAnc(u, v)) return u;
    if(isAnc(v, u)) return v;  
    return par[0][lift(u, v)];
}

int dsu[MAX];

int f(int node){
    if(dsu[node] < 0) return node;
    return dsu[node] = f(dsu[node]);
}

void unite(int u, int v){
    u = f(u), v = f(v);
    if(u == v) return;
    if(-dsu[u] < -dsu[v]) swap(u, v);
    dsu[u] += dsu[v];
    dsu[v] = u;  
}

vector<array<int, 2>> Q; 
vector<bool> ans;

int main(){
    memset(dsu, -1, sizeof(dsu));
    cin >> n >> m; 
    for(int i = 1; i <= n + m - 1; i++){
        string s; cin >> s;
        if(s[0] == 'S'){
            int u, v; cin >> u >> v;
            g[u].push_back({v, i});
            g[v].push_back({u, i});
            Q.push_back({-u, -v});
        }
        else{
            int u, a; cin >> u >> a;
            Q.push_back({a, u});
        }
    }
    dp[1][0] = 1;
    dp[1][1] = 1;
    dfs(1, 1);
    for(int i = 1; i <= n; i++){
        cout << dp[i][0] << ' ' << dp[i][1] << '\n';
    }
    for(int j = 1; j < LOGMAX; j++){
        for(int i = 1; i <= n; i++){
            par[j][i] = par[j - 1][par[j - 1][i]];
        }
    }
    for(auto a : Q){
        if(a[0] < 0){
            unite(-a[0], -a[1]);
            continue;
        }
        if(a[0] == a[1]){
            cout << "yes\n";
            continue;
        }
        if(f(a[0]) != f(a[1])){
            cout << "no\n";
            continue;
        }
        if(!isAnc(a[0], a[1]) && !isAnc(a[1], a[0]) && parl[lift(a[0], a[1])] > parl[lift(a[1], a[0])]){
            cout << "no\n";
            continue;
        }
        int l = lca(a[0], a[1]);
        if(h[dp[a[1]][1]] <= h[l] && h[dp[a[0]][0]] <= h[l]) cout << "yes\n";
        else cout << "no\n";
    }
}

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 16624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 16624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 16328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 16328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 16328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 16328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 16328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 16328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 16188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 16188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 16216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 16216 KB Output isn't correct
2 Halted 0 ms 0 KB -