oj.uz

Submission #659639

# Submission time Handle Problem Language Result Execution time Memory
659639 2022-11-18T20:41:13 Z someone Werewolf (IOI18_werewolf) C++14
0 / 100
 287 ms 39268 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 42;

vector<int> adj[N], req[N];
int n, m, q, sz[N], par[N];

int F1(int i) {
    if(sz[i] < 0)
        return i;
    return F1(sz[i]);
}

int F2(int i) {
    if(par[i] == i)
        return i;
    return par[i] = F2(par[i]);
}

void U1(int a, int b) {
    a = F1(a), b = F1(b);
    if(a == b)
        return;
    if(a > b)
        swap(a, b);
    sz[a] += sz[b];
    sz[b] = a;
}

void U2(int a, int b) {
    a = F2(a), b = F2(b);
    if(a < b)
        swap(a, b);
    par[b] = a;
}

int possible(int a, int b, int auth) {
    while(sz[a] >= auth)
        a = sz[a];
    while(sz[b] >= auth)
        b = sz[b];
    return a == b;
}

vector<int> check_validity(int NB, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = NB, m = X.size(), q = S.size();
    vector<int> ans(q);
    for(int i = 0; i < n; i++)
        par[i] = i, sz[i] = -1;
    for(int i = 0; i < m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    
    for(int i = n-1; i >= 0; i--)
        for(int j : adj[i])
            if(j > i)
                U1(i, j);
    
    for(int i = 0; i < q; i++)
        req[R[i]].push_back(i);
    
    for(int i = 0; i < n; i++) {
        for(int j : adj[i])
            if(j < i)
                U2(i, j);
        for(int j : req[i])
            ans[j] = possible(F2(E[j]), S[j], L[j]);
    }
    return ans;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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