oj.uz

답안 #1084216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1084216 2024-09-05T16:11:40 Z serifefedartar Inside information (BOI21_servers) C++17
2.5 / 100
 3500 ms 29436 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
 
tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> os;
vector<vector<pair<int,int>>> graph;
vector<array<int,3>> query;
vector<int> query_ids[MAXN];
int N, K, sz[MAXN], ans[MAXN], marked[MAXN], color[MAXN];
int ttt[MAXN], out_smallest[MAXN], out_greatest[MAXN], in_greatest[MAXN];

int get_sz(int node, int parent) {
    sz[node] = 1;
    for (auto u : graph[node]) {
        if (u.f != parent && !marked[u.f])
            sz[node] += get_sz(u.f, node);
    }
    return sz[node];
}

int find_centro(int node, int parent, int n) {
    for (auto u : graph[node]) {
        if (u.f != parent && !marked[u.f] && sz[u.f] * 2 >= n)
            return find_centro(u.f, node, n);
    }
    return node;
}

vector<int> V;
void dfs(int node, int parent, int minimum_edge, int last_edge) {
    V.push_back(node);
    out_smallest[node] = minimum_edge;
    out_greatest[node] = last_edge;
    for (auto u : graph[node]) {
        if (u.f == parent || marked[u.f])
            continue;
        if (u.s > last_edge)
            dfs(u.f, node, minimum_edge, u.s);
    }
}

void dfs2(int node, int parent, int minimum_edge, int maximum_edge) {
    V.push_back(node);
    in_greatest[node] = maximum_edge;
    for (auto u : graph[node]) {
        if (u.f == parent || marked[u.f])
            continue;
        if (u.s < minimum_edge)
            dfs2(u.f, node, u.s, maximum_edge);
    }
}

void dfs3(int node, int parent) {
    if (ttt[node] > 0 && in_greatest[node] <= ttt[node])
        ans[ttt[node]] += os.order_of_key({ttt[node], 1e9}) + 1;
    for (auto u : graph[node]) {
        if (u.f != parent && !marked[u.f])
            dfs3(u.f, node);
    }
}

void init(int node, int parent, int cc) {
    color[node] = cc;
    for (auto u : graph[node]) {
        if (u.f != parent && !marked[u.f])
            init(u.f, node, cc);
    }
}


void activate(int node, int parent) {
    if (out_smallest[node] != -1)
        os.insert({out_smallest[node], node});
    for (auto u : graph[node]) {
        if (u.f != parent && !marked[u.f])
            activate(u.f, node);
    }
}

void deactivate(int node, int parent) {
    if (out_smallest[node] != -1)
        os.erase({out_smallest[node], node});
    for (auto u : graph[node]) {
        if (u.f != parent && !marked[u.f])
            deactivate(u.f, node);
    }
}

void decompose(int node) {
    get_sz(node, node);
    int centro = find_centro(node, node, N);

    marked[centro] = true;
    color[centro] = -1;
    int cc = 0;
    os.clear();
    for (auto u : graph[centro]) {
        if (!marked[u.f]) {
            init(u.f, node, ++cc);
            dfs(u.f, node, u.s, u.s);
            dfs2(u.f, node, u.s, u.s);
            activate(u.f, node);
        }
    }

    for (auto id : query_ids[centro]) {
        array<int,3> Q = query[id];
        if (Q[0] == centro)
            ans[Q[2]] += (in_greatest[Q[1]] != -1 && in_greatest[Q[1]] < Q[2]);
        else if (Q[1] == centro)
            ans[Q[2]] += (out_greatest[Q[0]] != -1 && out_greatest[Q[0]] < Q[2]);
    }

    for (auto u : V) {
        for (auto id : query_ids[u]) {
            array<int,3> Q = query[id];
            ans[Q[2]] += (color[Q[1]] != color[Q[0]] && out_smallest[Q[0]] != -1 && in_greatest[Q[1]] != -1 
                            && in_greatest[Q[1]] < out_smallest[Q[0]] && out_greatest[Q[0]] < Q[2]);
        }
    }

    int deact = 0;
    for (auto u : graph[centro]) {
        if (!marked[u.f]) {
            while (deact + 1 <= graph[centro].size() && graph[centro][deact].s <= u.s) {
                deactivate(graph[centro][deact].f, node);
                deact++;
            }
            dfs3(u.f, node);
        }
    }

    for (auto u : V)
        in_greatest[u] = out_smallest[u] = out_greatest[u] = -1;
    V = vector<int>();

    for (auto u : graph[centro]) {
        if (!marked[u.f])
            decompose(u.f);
    }
}

int main() {
    fast;
    memset(in_greatest, -1, sizeof(in_greatest));
    memset(out_smallest, -1, sizeof(out_smallest));
    memset(out_greatest, -1, sizeof(out_greatest));
    cin >> N >> K;

    graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
    for (int i = 1; i <= N + K - 1; i++) {
        char ch;
        cin >> ch;
        if (ch == 'S') {
            int a, b;
            cin >> a >> b;
            graph[a].push_back({b, i});
            graph[b].push_back({a, i});
        } else if (ch == 'Q') {
            int a, b;
            cin >> a >> b;
            query_ids[a].push_back(query.size());
            query_ids[b].push_back(query.size());
            query.push_back({a, b, i});
        } else {
            int a;
            cin >> a;
            ttt[a] = i;
            query.push_back({a, -1, i});
        }
    }
    for (int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end(), [&](pair<int,int> A, pair<int,int> B) {
            return A.s < B.s;
        });
    }
    decompose(1);

    for (auto u : query) {
        if (u[1] != -1)
            cout << (ans[u[2]] || u[0] == u[1] ? "yes\n" : "no\n");
        else
            cout << ans[u[2]] << "\n";
    }
}

Compilation message

servers.cpp: In function 'void decompose(int)':
servers.cpp:134:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             while (deact + 1 <= graph[centro].size() && graph[centro][deact].s <= u.s) {
      |                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11280 KB Output is correct
2 Correct 36 ms 11536 KB Output is correct
3 Correct 38 ms 11784 KB Output is correct
4 Correct 142 ms 11592 KB Output is correct
5 Correct 218 ms 11780 KB Output is correct
6 Correct 31 ms 11776 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11280 KB Output is correct
2 Correct 36 ms 11536 KB Output is correct
3 Correct 38 ms 11784 KB Output is correct
4 Correct 142 ms 11592 KB Output is correct
5 Correct 218 ms 11780 KB Output is correct
6 Correct 31 ms 11776 KB Output is correct
7 Incorrect 20 ms 11280 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 11280 KB Output is correct
2 Incorrect 162 ms 29436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 11280 KB Output is correct
2 Incorrect 162 ms 29436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 11280 KB Output is correct
2 Execution timed out 3567 ms 27600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 11280 KB Output is correct
2 Execution timed out 3567 ms 27600 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11280 KB Output is correct
2 Incorrect 383 ms 25260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11280 KB Output is correct
2 Incorrect 383 ms 25260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 11280 KB Output is correct
2 Execution timed out 3581 ms 27560 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 11280 KB Output is correct
2 Execution timed out 3581 ms 27560 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11280 KB Output is correct
2 Correct 37 ms 11536 KB Output is correct
3 Correct 31 ms 11640 KB Output is correct
4 Correct 132 ms 11528 KB Output is correct
5 Correct 223 ms 11872 KB Output is correct
6 Correct 32 ms 11788 KB Output is correct
7 Correct 19 ms 11276 KB Output is correct
8 Incorrect 174 ms 29392 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 11280 KB Output is correct
2 Correct 37 ms 11536 KB Output is correct
3 Correct 31 ms 11640 KB Output is correct
4 Correct 132 ms 11528 KB Output is correct
5 Correct 223 ms 11872 KB Output is correct
6 Correct 32 ms 11788 KB Output is correct
7 Correct 19 ms 11276 KB Output is correct
8 Incorrect 174 ms 29392 KB Output isn't correct
9 Halted 0 ms 0 KB -