oj.uz

Submission #528913

# Submission time Handle Problem Language Result Execution time Memory
528913 2022-02-21T18:04:39 Z sare Inside information (BOI21_servers) C++17
50 / 100
 661 ms 99132 KB 
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
    string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
    string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
    return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
    bool fst = 1; string res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += to_string(x);
    }
    res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
    return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
#define all(x) (x).begin(), (x).end()
const int MAXN = 120010;
struct Fenwick {
    int fen[MAXN * 2];
    vector<int> his;

    inline void add (int ind) {
        for (ind += 2; ind; ind -= ind & -ind) {
            his.push_back(ind);
            fen[ind]++;
        }
    }

    inline int get (int ind) {
        int ret = 0;
        for (ind += 2; ind < 2 * MAXN; ind += ind & -ind) {
            ret += fen[ind];
        }
        return ret;
    }

    inline void clear () {
        for (int i : his) {
            fen[i] = 0;
        }
        his.clear();
    }
} fen;
struct Par {
    int v, lst, first;
    bool inc, dec;
};
struct Query {
    bool x;
    int v, u, t;
    bool ans0 = 0;
    int ans1 = 0;
};
struct Event {
    bool x;
    int l, r, ind;

    inline bool operator < (const Event& he) {
        return r < he.r;
    }
};
int n, q, sz[MAXN], out[MAXN];
vector<Par> par[MAXN];
vector<Query> query;
vector<Event> event[MAXN];
vector<pair<int, int>> adj[MAXN], query_add[MAXN];
bitset<MAXN> hide;

void dfs_size (int v, int p) {
    sz[v] = 1;
    for (auto [i, t] : adj[v]) {
        if (!hide[i] && i != p) {
            dfs_size(i, v);
            sz[v] += sz[i];
        }
    }
}
int centroid (int v, int p, int curn) {
    for (auto [i, t] : adj[v]) {
        if (i != p && !hide[i] && sz[i] * 2 > curn) {
            return centroid(i, v, curn);
        }
    }
    return v;
}

void dfs_build (int v, int p, int cent, int lst, int first, bool inc, bool dec) {
    // wis(v, cent, lst, first);
    par[v].push_back({cent, lst, first, inc, dec});
    if (inc && first != -1) {
        event[cent].push_back({0, first, lst});
    }
    for (auto [i, t] : adj[v]) {
        if (i == p || hide[i]) {
            continue;
        }
        bool tdec = dec && (lst == -1 || lst > t);
        bool tinc = inc && (lst == -1 || lst < t);
        dfs_build(i, v, cent, t, first == 0 ? t : first, tinc, tdec);
    }
}

void decompose (int v) {
    dfs_size(v, -1);
    v = centroid(v, -1, sz[v]);
    hide[v] = 1;
    dfs_build(v, -1, v, -1, 0, 1, 1);

    for (auto [i, t] : adj[v]) {
        if (!hide[i]) {
            decompose(i);
        }
    }
}

inline bool get0 (int v, int u, int t) {
    vector<int> tmp;
    for (auto& i : par[u]) {
        tmp.push_back(i.v);
    }
    int lca;
    sort(all(tmp));
    for (auto& i : par[v]) {
        if (binary_search(all(tmp), i.v)) {
            lca = i.v;
            break;
        }
    }
    // wis(u, v, lca);
    bool ret = 1;
    Par U, V;
    for (auto& i : par[u]) {
        if (i.v == lca) {
            U = i;
            ret &= i.dec;
            ret &= i.first < t;
        }
    }
    for (auto& i : par[v]) {
        if (i.v == lca) {
            V = i;
            ret &= i.inc;
            ret &= i.lst < t;
        }
    }
    // wis(V.lst);
    ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
    // wis(U.first, V.first);
    return ret;
}

inline void get1 (int v, int t, int ind) {
    for (auto& i : par[v]) {
        if (i.dec && i.first < t) {
            event[i.v].push_back({1, i.first, t, ind});
        }
    }
}

inline void finish (int v) {
    sort(all(event[v]));
    for (auto& i : event[v]) {
        if (i.x == 0) {
            fen.add(i.l);
        }
        else {
            query[i.ind].ans1 += fen.get(i.l) + 1;
        }
    }
    fen.clear();
}

int main() {
    ios::sync_with_stdio(0);
#ifndef LOCAL
    cin.tie(0);
#endif
    cin >> n >> q;
    query.reserve(q);
    for (int i = 1; i < n + q; i++) {
        char c;
        cin >> c;
        if (c == 'S') {
            int u, v;
            cin >> u >> v;
            u--, v--;
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }
        else if (c == 'Q') {
            int v, d;
            cin >> v >> d;
            v--, d--;
            query.push_back({0, v, d, i});
        }
        else {
            int d;
            cin >> d;
            d--;
            query.push_back({1, d, -1, i});
        }
    }
    decompose(0);
    for (int i = 0; i < n; i++) {
        reverse(all(par[i]));
    }
    
    for (int i = 0; i < q; i++) {
        if (query[i].x == 0) {
            query[i].ans0 = get0(query[i].v, query[i].u, query[i].t);
        }
        else {
            get1(query[i].v, query[i].t, i);
        }
    } 
    for (int i = 0; i < n; i++) {
        finish(i);
    }

    for (int i = 0; i < q; i++) {
        if (query[i].x == 0) {
            cout << (query[i].ans0 ? "yes" : "no") << '\n';
        }
        else {
            cout << query[i].ans1 << '\n';
            assert(false);
        }
    }
}

Compilation message

servers.cpp: In function 'bool get0(int, int, int)':
servers.cpp:168:25: warning: 'V.Par::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
  168 |     ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~
servers.cpp:168:41: warning: 'U.Par::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
  168 |     ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:161:9: warning: 'lca' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |         if (i.v == lca) {
      |         ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15044 KB Output is correct
2 Correct 78 ms 17616 KB Output is correct
3 Correct 51 ms 17484 KB Output is correct
4 Correct 101 ms 18184 KB Output is correct
5 Correct 73 ms 17880 KB Output is correct
6 Correct 42 ms 17092 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15044 KB Output is correct
2 Correct 78 ms 17616 KB Output is correct
3 Correct 51 ms 17484 KB Output is correct
4 Correct 101 ms 18184 KB Output is correct
5 Correct 73 ms 17880 KB Output is correct
6 Correct 42 ms 17092 KB Output is correct
7 Runtime error 51 ms 31708 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15072 KB Output is correct
2 Correct 170 ms 42924 KB Output is correct
3 Correct 159 ms 42844 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15072 KB Output is correct
2 Correct 170 ms 42924 KB Output is correct
3 Correct 159 ms 42844 KB Output is correct
4 Runtime error 43 ms 31216 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15044 KB Output is correct
2 Correct 425 ms 84368 KB Output is correct
3 Correct 439 ms 84356 KB Output is correct
4 Correct 396 ms 99104 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15044 KB Output is correct
2 Correct 425 ms 84368 KB Output is correct
3 Correct 439 ms 84356 KB Output is correct
4 Correct 396 ms 99104 KB Output is correct
5 Runtime error 57 ms 31500 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15048 KB Output is correct
2 Correct 400 ms 75340 KB Output is correct
3 Correct 347 ms 65320 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15048 KB Output is correct
2 Correct 400 ms 75340 KB Output is correct
3 Correct 347 ms 65320 KB Output is correct
4 Runtime error 50 ms 31444 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15068 KB Output is correct
2 Correct 442 ms 84316 KB Output is correct
3 Correct 421 ms 84320 KB Output is correct
4 Correct 388 ms 99132 KB Output is correct
5 Correct 43 ms 15964 KB Output is correct
6 Correct 357 ms 75320 KB Output is correct
7 Correct 376 ms 65348 KB Output is correct
8 Correct 501 ms 64444 KB Output is correct
9 Correct 479 ms 64864 KB Output is correct
10 Correct 548 ms 81108 KB Output is correct
11 Correct 555 ms 80740 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15068 KB Output is correct
2 Correct 442 ms 84316 KB Output is correct
3 Correct 421 ms 84320 KB Output is correct
4 Correct 388 ms 99132 KB Output is correct
5 Correct 43 ms 15964 KB Output is correct
6 Correct 357 ms 75320 KB Output is correct
7 Correct 376 ms 65348 KB Output is correct
8 Correct 501 ms 64444 KB Output is correct
9 Correct 479 ms 64864 KB Output is correct
10 Correct 548 ms 81108 KB Output is correct
11 Correct 555 ms 80740 KB Output is correct
12 Runtime error 62 ms 31428 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15108 KB Output is correct
2 Correct 76 ms 17616 KB Output is correct
3 Correct 65 ms 17532 KB Output is correct
4 Correct 134 ms 18104 KB Output is correct
5 Correct 77 ms 17880 KB Output is correct
6 Correct 49 ms 17116 KB Output is correct
7 Correct 36 ms 15948 KB Output is correct
8 Correct 183 ms 42940 KB Output is correct
9 Correct 187 ms 42924 KB Output is correct
10 Correct 51 ms 15976 KB Output is correct
11 Correct 445 ms 84376 KB Output is correct
12 Correct 512 ms 84316 KB Output is correct
13 Correct 453 ms 99084 KB Output is correct
14 Correct 53 ms 15948 KB Output is correct
15 Correct 432 ms 75260 KB Output is correct
16 Correct 423 ms 65328 KB Output is correct
17 Correct 582 ms 64372 KB Output is correct
18 Correct 575 ms 64900 KB Output is correct
19 Correct 661 ms 81136 KB Output is correct
20 Correct 623 ms 80584 KB Output is correct
21 Correct 300 ms 41740 KB Output is correct
22 Correct 241 ms 42276 KB Output is correct
23 Correct 354 ms 50768 KB Output is correct
24 Correct 355 ms 51236 KB Output is correct
25 Correct 494 ms 69752 KB Output is correct
26 Correct 483 ms 58028 KB Output is correct
27 Correct 387 ms 57796 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15108 KB Output is correct
2 Correct 76 ms 17616 KB Output is correct
3 Correct 65 ms 17532 KB Output is correct
4 Correct 134 ms 18104 KB Output is correct
5 Correct 77 ms 17880 KB Output is correct
6 Correct 49 ms 17116 KB Output is correct
7 Correct 36 ms 15948 KB Output is correct
8 Correct 183 ms 42940 KB Output is correct
9 Correct 187 ms 42924 KB Output is correct
10 Correct 51 ms 15976 KB Output is correct
11 Correct 445 ms 84376 KB Output is correct
12 Correct 512 ms 84316 KB Output is correct
13 Correct 453 ms 99084 KB Output is correct
14 Correct 53 ms 15948 KB Output is correct
15 Correct 432 ms 75260 KB Output is correct
16 Correct 423 ms 65328 KB Output is correct
17 Correct 582 ms 64372 KB Output is correct
18 Correct 575 ms 64900 KB Output is correct
19 Correct 661 ms 81136 KB Output is correct
20 Correct 623 ms 80584 KB Output is correct
21 Correct 300 ms 41740 KB Output is correct
22 Correct 241 ms 42276 KB Output is correct
23 Correct 354 ms 50768 KB Output is correct
24 Correct 355 ms 51236 KB Output is correct
25 Correct 494 ms 69752 KB Output is correct
26 Correct 483 ms 58028 KB Output is correct
27 Correct 387 ms 57796 KB Output is correct
28 Runtime error 53 ms 31684 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -