oj.uz

답안 #678339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678339 2023-01-05T13:32:11 Z 1bin 늑대인간 (IOI18_werewolf) C++14
0 / 100
 521 ms 107224 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int B = 1 << 18;
ll n, m, q, par[B], a, b, d[B][2], u[B][2], t;
vector<int> adj[B], seg[B * 2];
vector<int> g[B], vl[B], vr[B];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}

void dfs(int x, int f){
    !f ? d[x][0] = t++ : u[x][0] = t++;
    for(int& nx : g[x]) dfs(nx, f);
    !f ? d[x][1] = t - 1 : u[x][1] = t - 1;
    return;
}

int qry(int l, int r, int k){
    l += B; r += B;
    int ret = n;
    while(l <= r){
        if(l & 1){
            auto it = lower_bound(all(seg[l]), k);
            if(it != seg[l].end()) ret = min(ret, *it);
            l++;
        }
        if(!(r & 1)){
            auto it = lower_bound(all(seg[r]), k);
            if(it != seg[r].end()) ret = min(ret, *it);
            r--;
        }
        l /= 2; r /= 2;
    }
    return ret;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	n = N, m = X.size(), q = S.size();
	vector<int> A(q);
	for(int i = 0; i < m; i++){
	    a = X[i]; b = Y[i];
	    adj[a].emplace_back(b);
	    adj[b].emplace_back(a);
	}
	for(int i = 0; i < q; i++){
	   vl[L[i]].emplace_back(i);
	   vr[R[i]].emplace_back(i);
	}
	memset(par, -1, sizeof(par));
    for(int x = n - 1; x >= 0; x--){
        for(int y : adj[x]){
            if(y < x) continue;
            y = find(y);
            if(x == y) continue;
            par[y] = x;
            g[x].emplace_back(y);
        }
        for(int& i : vl[x])
            S[i] = find(S[i]);
    }
    dfs(0, 0);
    
    memset(par, -1, sizeof(par));
    for(int i = 0; i < n; i++) g[i].clear();
    for(int x = 0; x < n; x++) {
        for(int y : adj[x]){
            if(y > x) continue;
            y = find(y);
            if(x == y) continue;
            par[y] = x;
            g[x].emplace_back(y);
        }
        for(int& i : vr[x])
            E[i] = find(E[i]);
    }
    t = 0; dfs(n - 1, 1);
    for(int i = 0; i < n; i++) seg[B + u[i][0]].emplace_back(i);
    for(int i = B - 1; i; i--){
        seg[i].resize(seg[i * 2].size() + seg[i * 2 + 1].size());
        merge(all(seg[i * 2]), all(seg[i * 2 + 1]), seg[i].begin());
    }
    for(int i = 0; i < q; i++){
        a = u[E[i]][0]; b = u[E[i]][1];
        if(qry(a, b, S[i]) == S[i]) A[i] = 1;
        else A[i] = 0;
        //cout << A[i] << ' ';
    }
	return A;
}

/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> q;
    vector<int> X(m), Y(m), S(q), E(q), L(q), R(q);
    for(int i = 0; i < m; i++) cin >> X[i] >> Y[i];
    for(int i = 0; i < q; i++) cin >> S[i] >> E[i] >> L[i] >> R[i];
    check_validity(n, X, Y, S, E, L, R);
    return 0;
}*/

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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