oj.uz

Submission #677770

# Submission time Handle Problem Language Result Execution time Memory
677770 2023-01-04T10:52:07 Z someone Werewolf (IOI18_werewolf) C++14
0 / 100
 618 ms 71952 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 42;
 
set<int> vals[N];
vector<int> adj[N], fils[N], req[N];
int n, m, q, id = 0, sz[N], par[N], pds[N], deb[N], fin[N];
 
int F(int i) {
    if(par[i] == i)
        return i;
    return par[i] = F(par[i]);
}

void U(int a, int b) {
    a = F(a), b = F(b);
    if(a == b) return;
    if((int)vals[a].size() < (int)vals[b].size())
        swap(a, b);
    par[b] = a;
    for(int i : vals[b])
        vals[a].insert(i);
    vals[b].clear();
}

int nbit = 0;

void dfs(int i) {
    deb[i] = id++;
    for(int j : fils[i])
        dfs(j);
    fin[i] = id;
}

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 = (int)X.size(), q = (int)S.size();
    vector<int> ans(q);
    for(int i = 0; i < n; i++)
        par[i] = i;
    for(int i = 0; i < m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    for(int i = 0; i < q; i++)
        req[L[i]].push_back(i);
    
    for(int i = n-1; i >= 0; i--) {
        for(int j : adj[i])
            if(j > i) {
                j = F(j);
                if(i != j) {
                    fils[i].push_back(j);
                    par[j] = i;
                }
            }
        for(int j : req[i])
            S[j] = F(S[j]);
    }
    for(int i = 0; i < n; i++)
        req[i].clear();
    dfs(0);
    for(int i = 0; i < q; i++)
        req[L[i]].push_back(i);
    for(int i = 0; i < n; i++) {
        par[i] = i;
        vals[i].insert(deb[i]);
    }
    for(int i = 0; i < n; i++) {
        for(int j : adj[i])
            if(j < i)
                U(i, j);
        for(int j : req[i]) {
            auto it = vals[F(E[j])].lower_bound(deb[S[j]]);
            if(it != vals[F(E[j])].end() && (*it) < fin[S[j]])
                ans[j] = 1;
        }
    }
    return ans;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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