oj.uz

Submission #409077

# Submission time Handle Problem Language Result Execution time Memory
409077 2021-05-20T07:02:51 Z balbit Inside information (BOI21_servers) C++14
55 / 100
 3500 ms 58760 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 240000+5;

struct edge{
    int u, t;
};
vector<edge> g[maxn];
vector<int> cnt[maxn];
//vector<int> frm[maxn];

int now[maxn];
int ans[maxn*2];
vector<int> hey[maxn];
vector<int> hey2[maxn];
struct havequery{
    int a,b,t;
};

int inc[maxn], decr[maxn];
int par[maxn], parw[maxn]; // parent and parent weight
int fa[21][maxn];
int dep[maxn];
int L[maxn], R[maxn];
int IT = 0;
bool ispar(int a, int b) {
    return L[a] <= L[b] && R[a] >= R[b];
}
void dfs(int v, int p) {
    L[v] =R[v]=IT++;
    for (edge e : g[v]) {
        int u = e.u;
        if (u != p) {
            fa[0][u] = v;
            par[u] = v; parw[u] = e.t;
            dep[u] = dep[v] + 1;
            inc[u] = decr[u] = v;
            if (parw[u] > parw[v]) {
                inc[u] = inc[v];
            }
            else{
                decr[u] = decr[v];
            }
            if (v != 0) {
                assert(parw[u] != parw[v]);
            }
            dfs(u,v);
            R[v] = R[u];
        }
    }
}

int kth(int a, int k) {
    for (int j = 0; j<=20; ++j) {
        if (k & (1<<j)) a = fa[j][a];
    }
    return a;
}

pii LCA(int a, int b) {
    bool swp = 0;
    if (dep[a] < dep[b]) {
        swap(a,b); swp = 1;
    }
    a = kth(a, dep[a] - dep[b]);
    if (a == b) return {a,b};
    assert(dep[a] == dep[b]);
    for (int j = 20; j>=0; --j) {
        if (fa[j][a] != fa[j][b]) {
            a = fa[j][a]; b = fa[j][b];
        }
    }
    assert(a!=b);
    if (swp) swap(a,b);
    return {a,b};
}


bool yes(havequery HH){
    int a = HH.a, b = HH.b;
    if (a == b) {
        return 1;
    }
    swap(a,b); // walking from a to b!!!!!

    pii lol = ispar(b,a)?pii{b,b}:LCA(a,b);
    int A = lol.f, B = lol.s;
    int C = A==B?A:par[A];
//    if (A!=B) assert(par[A] == par[B]);

    if (dep[inc[b]] > dep[C] || dep[decr[a]] > dep[C]) {
        return 0;
    }

    if (A!=B) {
        if (parw[A] > parw[B]) {
            return 0;
        }
    }

    int hoho = HH.t;
    int lstedge;

    if (C == b) {
        int thon = kth(a, dep[a] - dep[C] - 1);
        assert(par[thon] == C);
        lstedge = parw[thon];
    }else{
        lstedge = parw[b];
    }
    if (lstedge > HH.t) {
        return 0;
    }

    return 1;
}

int pa[maxn], pb[maxn];
bool isedge[maxn];

signed main(){
    IOS();
    int n,q; cin>>n>>q; q += n-1;
    vector<havequery> hv;
//    fill(ans, ans+maxn, 20202930);
    vector<pair<pii, int> > E;
//    REP(i,n) here[i].pb(i), nof[i] = 1;
    vector<pii> hmm;
    REP(i,q) {
        char c; cin>>c;
        if (c == 'S') {
            int a,b; cin>>a>>b; --a; --b;
            pa[i] = a; pb[i] =b; isedge[i] = 1;
            g[a].pb({b,i});
            g[b].pb({a,i});
            E.pb({{a,b},i});
            ans[i] = 202022020;

        }
        if (c == 'Q') {
            int a, b; cin>>a>>b; --a; --b;
            hv.pb({a,b,i});

        }
        if (c == 'C') {
            int a; cin>>a; --a;
//            ans[i] = nof[a];
            hey[a].pb(i);
            hey2[a].pb(i);
            hmm.pb({a,i});
        }
    }
    dfs(0, -1);
    REP1(j, 20) REP(i,n) fa[j][i] = fa[j-1][fa[j-1][i]];
    reverse(ALL(E));
    fill(now, now+maxn, 1);
    const int BS = 300;
    int start = 0; while (start + BS<=q) start += BS;
    bug(start);
    for (int T = start; T >=0; T-=BS){

        fill(now, now+maxn, 1);
        for( auto P : E) {
            if (P.s >= T) continue;
            int a = P.f.f, b=P.f.s;
            int tm = P.s;
//            bug(a,b,tm);
            for (int v : {a,b}) {
                while (!hey[v].empty()) {
                    if (hey[v].back() >= T-1) {
                        ans[hey[v].back()] -= now[v];
                        hey[v].pop_back();
                    }else break;
                }
            }
            int nw = now[a] + now[b];
            now[a] = now[b] = nw;
        }
        REP(i,n) {
            while (!hey[i].empty() ) {
                if (hey[i].back() >= T-1) {
                    ans[hey[i].back()] -= now[i];
                    hey[i].pop_back();
                }else break;
            }
        }

        REP(i,n) {
            while (!hey2[i].empty()) {
                if (hey2[i].back() >= T-1){
                    ans[hey2[i].back()] += 1 + now[i];
                    hey2[i].pop_back();
                }
                else break;
            }
        }
    }
//    fill(now, now+maxn, 1);

    {
        for (havequery HH : hv) {
//            continue;
            ans[HH.t] = yes(HH)?-1:-2;
            // is the path from a
        }
    }
    for (pii p : hmm) {
        int v = p.f; int ansi = p.s;
//        ans[ansi] = 1;
//        REP(i,n) ans[ansi] += yes({i,v,ansi});
//        continue;
        int tk = 0;
        while (tk -1 <= ansi) tk += BS;
        tk -= BS;

        for (int i = tk; i <= ansi; ++i) {
            bug(i, ansi);
            if (!isedge[i]) continue;
            int a = pa[i], b= pb[i];
            if (dep[a] > dep[b]) swap(a,b);
            if (ispar(b,v)) {
                swap(a,b);
            }
            // i want b!
            ans[ansi] += yes({b,v,ansi});
        }
    }
    int nnn = 0;
    REP(i,q) {
        assert(ans[i] != 0);
        if (ans[i] < 10000000) {
            ++nnn;
            if (ans[i] > 0) cout<<ans[i]<<endl;
            else cout<<(ans[i] == -1?"yes":"no")<<endl;
        }
    }
    assert(nnn == (q-n+1));

}

/*
6 16
S 3 4
Q 3 4
Q 4 3
C 1
C 2
Q 2 4
Q 4 2
S 2 6
C 2
C 4
S 1 2
S 2 3
C 3
Q 5 4
S 2 5
Q 5 4
Q 2 4
C 4
C 3
Q 1 4
C 5
*/

Compilation message

servers.cpp: In function 'bool yes(havequery)':
servers.cpp:151:9: warning: unused variable 'hoho' [-Wunused-variable]
  151 |     int hoho = HH.t;
      |         ^~~~
servers.cpp: In function 'int main()':
servers.cpp:216:17: warning: unused variable 'tm' [-Wunused-variable]
  216 |             int tm = P.s;
      |                 ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 26804 KB Output is correct
2 Correct 86 ms 27896 KB Output is correct
3 Correct 85 ms 28116 KB Output is correct
4 Correct 92 ms 28032 KB Output is correct
5 Correct 82 ms 27340 KB Output is correct
6 Correct 87 ms 27204 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 26804 KB Output is correct
2 Correct 86 ms 27896 KB Output is correct
3 Correct 85 ms 28116 KB Output is correct
4 Correct 92 ms 28032 KB Output is correct
5 Correct 82 ms 27340 KB Output is correct
6 Correct 87 ms 27204 KB Output is correct
7 Correct 66 ms 26792 KB Output is correct
8 Correct 144 ms 28548 KB Output is correct
9 Correct 113 ms 28532 KB Output is correct
10 Correct 149 ms 28640 KB Output is correct
11 Correct 117 ms 27888 KB Output is correct
12 Correct 143 ms 27936 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26756 KB Output is correct
2 Correct 1110 ms 48068 KB Output is correct
3 Correct 1047 ms 48140 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26756 KB Output is correct
2 Correct 1110 ms 48068 KB Output is correct
3 Correct 1047 ms 48140 KB Output is correct
4 Correct 66 ms 26832 KB Output is correct
5 Correct 1698 ms 48260 KB Output is correct
6 Correct 1833 ms 48780 KB Output is correct
7 Correct 2304 ms 48684 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 26812 KB Output is correct
2 Correct 1018 ms 56488 KB Output is correct
3 Correct 1036 ms 56488 KB Output is correct
4 Correct 745 ms 56488 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 26812 KB Output is correct
2 Correct 1018 ms 56488 KB Output is correct
3 Correct 1036 ms 56488 KB Output is correct
4 Correct 745 ms 56488 KB Output is correct
5 Correct 60 ms 26760 KB Output is correct
6 Execution timed out 3587 ms 58728 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26720 KB Output is correct
2 Correct 792 ms 48316 KB Output is correct
3 Correct 1188 ms 48520 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26720 KB Output is correct
2 Correct 792 ms 48316 KB Output is correct
3 Correct 1188 ms 48520 KB Output is correct
4 Correct 65 ms 26716 KB Output is correct
5 Correct 2649 ms 50332 KB Output is correct
6 Execution timed out 3601 ms 50264 KB Time limit exceeded

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26804 KB Output is correct
2 Correct 1072 ms 56488 KB Output is correct
3 Correct 1024 ms 56492 KB Output is correct
4 Correct 734 ms 56488 KB Output is correct
5 Correct 64 ms 26804 KB Output is correct
6 Correct 783 ms 48200 KB Output is correct
7 Correct 1230 ms 48504 KB Output is correct
8 Correct 1389 ms 49332 KB Output is correct
9 Correct 1065 ms 49052 KB Output is correct
10 Correct 1040 ms 53364 KB Output is correct
11 Correct 1204 ms 52808 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26804 KB Output is correct
2 Correct 1072 ms 56488 KB Output is correct
3 Correct 1024 ms 56492 KB Output is correct
4 Correct 734 ms 56488 KB Output is correct
5 Correct 64 ms 26804 KB Output is correct
6 Correct 783 ms 48200 KB Output is correct
7 Correct 1230 ms 48504 KB Output is correct
8 Correct 1389 ms 49332 KB Output is correct
9 Correct 1065 ms 49052 KB Output is correct
10 Correct 1040 ms 53364 KB Output is correct
11 Correct 1204 ms 52808 KB Output is correct
12 Correct 61 ms 26756 KB Output is correct
13 Execution timed out 3573 ms 58696 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 26836 KB Output is correct
2 Correct 94 ms 27860 KB Output is correct
3 Correct 85 ms 28000 KB Output is correct
4 Correct 90 ms 27980 KB Output is correct
5 Correct 82 ms 27356 KB Output is correct
6 Correct 87 ms 27308 KB Output is correct
7 Correct 62 ms 26916 KB Output is correct
8 Correct 1078 ms 48064 KB Output is correct
9 Correct 971 ms 48160 KB Output is correct
10 Correct 66 ms 26816 KB Output is correct
11 Correct 978 ms 56488 KB Output is correct
12 Correct 984 ms 56636 KB Output is correct
13 Correct 735 ms 56492 KB Output is correct
14 Correct 65 ms 26808 KB Output is correct
15 Correct 772 ms 48544 KB Output is correct
16 Correct 1279 ms 48532 KB Output is correct
17 Correct 1283 ms 49332 KB Output is correct
18 Correct 1065 ms 48948 KB Output is correct
19 Correct 959 ms 53360 KB Output is correct
20 Correct 1229 ms 52732 KB Output is correct
21 Correct 1112 ms 48060 KB Output is correct
22 Correct 1006 ms 48100 KB Output is correct
23 Correct 1074 ms 48528 KB Output is correct
24 Correct 1120 ms 48624 KB Output is correct
25 Correct 1098 ms 50236 KB Output is correct
26 Correct 1199 ms 48916 KB Output is correct
27 Correct 1120 ms 47944 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 26836 KB Output is correct
2 Correct 94 ms 27860 KB Output is correct
3 Correct 85 ms 28000 KB Output is correct
4 Correct 90 ms 27980 KB Output is correct
5 Correct 82 ms 27356 KB Output is correct
6 Correct 87 ms 27308 KB Output is correct
7 Correct 62 ms 26916 KB Output is correct
8 Correct 1078 ms 48064 KB Output is correct
9 Correct 971 ms 48160 KB Output is correct
10 Correct 66 ms 26816 KB Output is correct
11 Correct 978 ms 56488 KB Output is correct
12 Correct 984 ms 56636 KB Output is correct
13 Correct 735 ms 56492 KB Output is correct
14 Correct 65 ms 26808 KB Output is correct
15 Correct 772 ms 48544 KB Output is correct
16 Correct 1279 ms 48532 KB Output is correct
17 Correct 1283 ms 49332 KB Output is correct
18 Correct 1065 ms 48948 KB Output is correct
19 Correct 959 ms 53360 KB Output is correct
20 Correct 1229 ms 52732 KB Output is correct
21 Correct 1112 ms 48060 KB Output is correct
22 Correct 1006 ms 48100 KB Output is correct
23 Correct 1074 ms 48528 KB Output is correct
24 Correct 1120 ms 48624 KB Output is correct
25 Correct 1098 ms 50236 KB Output is correct
26 Correct 1199 ms 48916 KB Output is correct
27 Correct 1120 ms 47944 KB Output is correct
28 Correct 66 ms 26676 KB Output is correct
29 Correct 147 ms 28544 KB Output is correct
30 Correct 112 ms 28556 KB Output is correct
31 Correct 156 ms 28652 KB Output is correct
32 Correct 120 ms 27920 KB Output is correct
33 Correct 124 ms 27824 KB Output is correct
34 Correct 66 ms 26732 KB Output is correct
35 Correct 1753 ms 48360 KB Output is correct
36 Correct 1719 ms 48864 KB Output is correct
37 Correct 2252 ms 48688 KB Output is correct
38 Correct 61 ms 26684 KB Output is correct
39 Execution timed out 3572 ms 58760 KB Time limit exceeded
40 Halted 0 ms 0 KB -