Submission #528921

#	Time	Username	Problem	Language	Result	Execution time	Memory
528921		sare	Inside information (BOI21_servers)	C++17	100 / 100	640 ms	104340 KiB

servers

//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 (stderr)

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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5