Submission #594739

#	Time	Username	Problem	Language	Result	Execution time	Memory
594739		SlavicG	Werewolf (IOI18_werewolf)	C++17	0 / 100	399 ms	54928 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;

const int N = 2e5 + 10;
int fen[N];
void modif(int u, int val) {
    for(int i = u + 1; i < N; i += i & -i) fen[i] += val;
}
int query(int l, int r) {
    int ans = 0;
    for(int i = r + 1; i > 0; i -= i & -i) ans += fen[i];
    for(int i = l; i > 0; i -= i & -i) ans += fen[i];
    return ans;
}

struct dsu {
    vector<int> p;
    dsu(int n) {
        p.resize(n); iota(p.begin(), p.end(), 0);
    }
    int get(int a) {
        return (a == p[a] ? a : get(p[a]));
    }
    void uni(int a, int b) {
        a = get(a), b = get(b);
        if(a == b) return;
        p[a] = b;
    }
};

void dfs(int u, vector<int>& p, vector<int>& s, vector<vector<int>>& adj, int& tt) {
    p[u] = tt++;
    s[u] = 1;
    for(int v: adj[u]) {
        dfs(v, p, s, adj, tt);
        s[u] += s[v];
    }
}

std::vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, std::vector<int> E,
vector<int> L, std::vector<int> R) {
    int Q = S.size(), paiu = 0, moment = 0;
    vector<int> ans(Q, 0);
    vector<vector<int>> g1(n), g2(n), g(n);
    for(int i = 0; i < X.size(); ++i) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    dsu d1(n), d2(n);

    for(int i = n - 1; i >= 0; --i) {
        set<int> st;
        for(int j: g[i]) {
            if(i < j) st.insert(d1.get(j));
        }
        for(auto x: st) {
            g1[i].push_back(d1.get(x));
            d1.uni(x, i);
        }
    }

    for(int i = 0; i < n; ++i) {
        set<int> st;
        for(int j: g[i]) {
            if(i > j) st.insert(d2.get(j));
        }
        for(auto x: st) {
            g2[i].push_back(d2.get(x));
            d2.uni(x, i);
        }
    }
    vector<int> p1(n), s1(n), p2(n), s2(n);
    dfs(d1.get(0), p1, s1, g1, paiu);
    dfs(d2.get(n - 1), p2, s2, g2, moment);
    vector<int> events[n], nodes(n);
    for(int i = 0; i < n; ++i) nodes[p1[i]] = p2[i];
    for(int i = 0; i < Q; ++i) {
        int node = L[i];
        events[p1[node]].push_back(-1);
        events[p1[node] + s1[node] - 1].push_back(i);
    }

    for(int i = 0; i < n; ++i) {
        sort(events[i].begin(), events[i].end());
        for(int j: events[i]) {
            if(j < 0) {
                modif(nodes[i], 1);
            } else {
                int node = R[j];
                int nodeL = L[j];
                if(query(p2[node], p2[node] + s2[node] - 1)) {
                    if(p1[nodeL] <= p1[S[j]] && p1[S[j]] <= i && p2[node] <= p2[E[j]] && p2[E[j]] <= p2[node] + s2[node] - 1) {
                        ans[j] = 1;
                    }
                }
            }
        }
        for(int j: events[i]) if(j >= 0) modif(nodes[i], -1);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < X.size(); ++i) {
      |                    ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51