oj.uz

Submission #528921

# Submission time Handle Problem Language Result Execution time Memory
528921 2022-02-21T18:28:18 Z sare Inside information (BOI21_servers) C++17
100 / 100
 640 ms 104340 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;
    }
};
inline string to_string (Event E) {
    return "(" + to_string(E.x) + ", " + to_string(E.l) + ", " + to_string(E.r) + ", " + to_string(E.ind) + ")";
}
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 != 0) {
        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;
        }
    }
    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;
        }
    }
    ret &= U.first == 0 || V.first == 0 || 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]));
    wis(v, event[v]);
    for (auto& i : event[v]) {
        if (i.x == 0) {
            fen.add(i.l);
        }
        else {
            int add = fen.get(i.l + 1);
            wis(v, query[i.ind].v, add);
            query[i.ind].ans1 += add + 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';
        }
    }
}

Compilation message

servers.cpp: In function 'void finish(int)':
servers.cpp:34:18: warning: statement has no effect [-Wunused-value]
   34 | #define wis(...) 0
      |                  ^
servers.cpp:183:5: note: in expansion of macro 'wis'
  183 |     wis(v, event[v]);
      |     ^~~
servers.cpp:34:18: warning: statement has no effect [-Wunused-value]
   34 | #define wis(...) 0
      |                  ^
servers.cpp:190:13: note: in expansion of macro 'wis'
  190 |             wis(v, query[i.ind].v, add);
      |             ^~~
servers.cpp: In function 'bool get0(int, int, int)':
servers.cpp:169:25: warning: 'V.Par::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
  169 |     ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~
servers.cpp:169:41: warning: 'U.Par::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
  169 |     ret &= U.first == 0 || V.first == 0 || U.first <= V.first;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:163:9: warning: 'lca' may be used uninitialized in this function [-Wmaybe-uninitialized]
  163 |         if (i.v == lca) {
      |         ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15048 KB Output is correct
2 Correct 74 ms 16144 KB Output is correct
3 Correct 48 ms 16092 KB Output is correct
4 Correct 116 ms 16768 KB Output is correct
5 Correct 91 ms 16380 KB Output is correct
6 Correct 42 ms 15632 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15048 KB Output is correct
2 Correct 74 ms 16144 KB Output is correct
3 Correct 48 ms 16092 KB Output is correct
4 Correct 116 ms 16768 KB Output is correct
5 Correct 91 ms 16380 KB Output is correct
6 Correct 42 ms 15632 KB Output is correct
7 Correct 43 ms 15516 KB Output is correct
8 Correct 70 ms 19764 KB Output is correct
9 Correct 64 ms 19632 KB Output is correct
10 Correct 77 ms 20192 KB Output is correct
11 Correct 78 ms 20888 KB Output is correct
12 Correct 46 ms 18744 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15120 KB Output is correct
2 Correct 135 ms 36464 KB Output is correct
3 Correct 134 ms 36352 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15120 KB Output is correct
2 Correct 135 ms 36464 KB Output is correct
3 Correct 134 ms 36352 KB Output is correct
4 Correct 34 ms 15428 KB Output is correct
5 Correct 159 ms 39912 KB Output is correct
6 Correct 136 ms 39892 KB Output is correct
7 Correct 122 ms 44364 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15044 KB Output is correct
2 Correct 429 ms 77652 KB Output is correct
3 Correct 389 ms 77760 KB Output is correct
4 Correct 373 ms 92184 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15044 KB Output is correct
2 Correct 429 ms 77652 KB Output is correct
3 Correct 389 ms 77760 KB Output is correct
4 Correct 373 ms 92184 KB Output is correct
5 Correct 46 ms 15468 KB Output is correct
6 Correct 433 ms 83276 KB Output is correct
7 Correct 389 ms 104340 KB Output is correct
8 Correct 413 ms 84940 KB Output is correct
9 Correct 399 ms 84952 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15024 KB Output is correct
2 Correct 333 ms 68740 KB Output is correct
3 Correct 345 ms 58976 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15024 KB Output is correct
2 Correct 333 ms 68740 KB Output is correct
3 Correct 345 ms 58976 KB Output is correct
4 Correct 45 ms 15428 KB Output is correct
5 Correct 375 ms 82292 KB Output is correct
6 Correct 374 ms 64976 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15044 KB Output is correct
2 Correct 428 ms 77696 KB Output is correct
3 Correct 388 ms 77708 KB Output is correct
4 Correct 370 ms 92328 KB Output is correct
5 Correct 56 ms 15052 KB Output is correct
6 Correct 331 ms 68668 KB Output is correct
7 Correct 336 ms 59060 KB Output is correct
8 Correct 406 ms 57800 KB Output is correct
9 Correct 396 ms 58404 KB Output is correct
10 Correct 493 ms 75552 KB Output is correct
11 Correct 492 ms 74848 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15044 KB Output is correct
2 Correct 428 ms 77696 KB Output is correct
3 Correct 388 ms 77708 KB Output is correct
4 Correct 370 ms 92328 KB Output is correct
5 Correct 56 ms 15052 KB Output is correct
6 Correct 331 ms 68668 KB Output is correct
7 Correct 336 ms 59060 KB Output is correct
8 Correct 406 ms 57800 KB Output is correct
9 Correct 396 ms 58404 KB Output is correct
10 Correct 493 ms 75552 KB Output is correct
11 Correct 492 ms 74848 KB Output is correct
12 Correct 61 ms 16008 KB Output is correct
13 Correct 414 ms 83312 KB Output is correct
14 Correct 418 ms 104312 KB Output is correct
15 Correct 393 ms 84932 KB Output is correct
16 Correct 416 ms 85024 KB Output is correct
17 Correct 43 ms 16324 KB Output is correct
18 Correct 374 ms 82384 KB Output is correct
19 Correct 367 ms 64916 KB Output is correct
20 Correct 414 ms 64120 KB Output is correct
21 Correct 411 ms 63424 KB Output is correct
22 Correct 478 ms 86080 KB Output is correct
23 Correct 612 ms 94388 KB Output is correct
24 Correct 568 ms 85060 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15080 KB Output is correct
2 Correct 74 ms 16132 KB Output is correct
3 Correct 49 ms 17348 KB Output is correct
4 Correct 100 ms 18148 KB Output is correct
5 Correct 101 ms 17732 KB Output is correct
6 Correct 44 ms 17092 KB Output is correct
7 Correct 33 ms 15964 KB Output is correct
8 Correct 131 ms 37412 KB Output is correct
9 Correct 183 ms 37492 KB Output is correct
10 Correct 63 ms 16040 KB Output is correct
11 Correct 420 ms 78808 KB Output is correct
12 Correct 391 ms 78104 KB Output is correct
13 Correct 389 ms 93372 KB Output is correct
14 Correct 41 ms 15940 KB Output is correct
15 Correct 340 ms 69888 KB Output is correct
16 Correct 336 ms 60280 KB Output is correct
17 Correct 440 ms 58988 KB Output is correct
18 Correct 404 ms 59756 KB Output is correct
19 Correct 464 ms 76640 KB Output is correct
20 Correct 518 ms 75496 KB Output is correct
21 Correct 156 ms 35132 KB Output is correct
22 Correct 156 ms 35500 KB Output is correct
23 Correct 302 ms 44132 KB Output is correct
24 Correct 276 ms 44308 KB Output is correct
25 Correct 414 ms 62908 KB Output is correct
26 Correct 419 ms 51528 KB Output is correct
27 Correct 344 ms 51364 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 15080 KB Output is correct
2 Correct 74 ms 16132 KB Output is correct
3 Correct 49 ms 17348 KB Output is correct
4 Correct 100 ms 18148 KB Output is correct
5 Correct 101 ms 17732 KB Output is correct
6 Correct 44 ms 17092 KB Output is correct
7 Correct 33 ms 15964 KB Output is correct
8 Correct 131 ms 37412 KB Output is correct
9 Correct 183 ms 37492 KB Output is correct
10 Correct 63 ms 16040 KB Output is correct
11 Correct 420 ms 78808 KB Output is correct
12 Correct 391 ms 78104 KB Output is correct
13 Correct 389 ms 93372 KB Output is correct
14 Correct 41 ms 15940 KB Output is correct
15 Correct 340 ms 69888 KB Output is correct
16 Correct 336 ms 60280 KB Output is correct
17 Correct 440 ms 58988 KB Output is correct
18 Correct 404 ms 59756 KB Output is correct
19 Correct 464 ms 76640 KB Output is correct
20 Correct 518 ms 75496 KB Output is correct
21 Correct 156 ms 35132 KB Output is correct
22 Correct 156 ms 35500 KB Output is correct
23 Correct 302 ms 44132 KB Output is correct
24 Correct 276 ms 44308 KB Output is correct
25 Correct 414 ms 62908 KB Output is correct
26 Correct 419 ms 51528 KB Output is correct
27 Correct 344 ms 51364 KB Output is correct
28 Correct 46 ms 15564 KB Output is correct
29 Correct 67 ms 19792 KB Output is correct
30 Correct 53 ms 19572 KB Output is correct
31 Correct 103 ms 20176 KB Output is correct
32 Correct 74 ms 20960 KB Output is correct
33 Correct 43 ms 18704 KB Output is correct
34 Correct 39 ms 16224 KB Output is correct
35 Correct 151 ms 39892 KB Output is correct
36 Correct 135 ms 39884 KB Output is correct
37 Correct 131 ms 44432 KB Output is correct
38 Correct 49 ms 16336 KB Output is correct
39 Correct 412 ms 83172 KB Output is correct
40 Correct 397 ms 104256 KB Output is correct
41 Correct 392 ms 84948 KB Output is correct
42 Correct 404 ms 84908 KB Output is correct
43 Correct 42 ms 16396 KB Output is correct
44 Correct 387 ms 82380 KB Output is correct
45 Correct 383 ms 65012 KB Output is correct
46 Correct 453 ms 64144 KB Output is correct
47 Correct 456 ms 63468 KB Output is correct
48 Correct 472 ms 85948 KB Output is correct
49 Correct 616 ms 94376 KB Output is correct
50 Correct 640 ms 85040 KB Output is correct
51 Correct 158 ms 44772 KB Output is correct
52 Correct 159 ms 46612 KB Output is correct
53 Correct 131 ms 44592 KB Output is correct
54 Correct 131 ms 41044 KB Output is correct
55 Correct 157 ms 40664 KB Output is correct
56 Correct 328 ms 49724 KB Output is correct
57 Correct 380 ms 70960 KB Output is correct
58 Correct 480 ms 67880 KB Output is correct
59 Correct 365 ms 56324 KB Output is correct