oj.uz

답안 #594714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594714 2022-07-12T21:08:47 Z SlavicG 늑대인간 (IOI18_werewolf) C++17
0 / 100
 328 ms 55276 KB 
#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 p[a] = (a == p[a] ? a : get(p[a]));
    }
    void uni(int a, int b, vector<vector<int>>& adj) {
        a = get(a), b = get(b);
        if(a == b) return;
        p[a] = b; adj[b].push_back(a);
    }
};

void dfs(int u, vector<int>& p, vector<int>& s, vector<vector<int>>& adj, int tt = 0) {
    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();
    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 = 0; i < n; ++i) {
        for(int j: g[i]) if(i > j) d1.uni(i, j, g1);
    }
    for(int i = n - 1; i >= 0; --i) {
        for(int j: g[i]) if(i < j) d2.uni(i, j, g2);
    }
    vector<int> p1(n), s1(n), p2(n), s2(n);
    dfs(d1.get(0), p1, s1, g1), dfs(d2.get(n - 1), p2, s2, g2);
    vector<int> events[n];
    for(int i = 0; i < Q; ++i) {
        int node = d1.get(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(i, 1);
            } else {
                int node = d2.get(R[j]);
                if(query(p2[node], p2[node] + s2[node] - 1)) ans[j] = 1;
            }
        }
        for(int j: events[i]) if(j >= 0) modif(i, -1);
    }
    return ans;
}

Compilation message

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.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

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