Submission #409066

# Submission time Handle Problem Language Result Execution time Memory
409066 2021-05-20T06:51:50 Z balbit Inside information (BOI21_servers) C++14
50 / 100
361 ms 56704 KB
#include <bits/stdc++.h>
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 = 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 = 10000;
    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) {
//        for (int tt : hey2[i]) ans[tt] += 1 + now[i];
//    }
//    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:150:9: warning: unused variable 'hoho' [-Wunused-variable]
  150 |     int hoho = HH.t;
      |         ^~~~
# Verdict Execution time Memory Grader output
1 Correct 60 ms 26808 KB Output is correct
2 Correct 82 ms 27836 KB Output is correct
3 Correct 83 ms 28040 KB Output is correct
4 Correct 83 ms 28140 KB Output is correct
5 Correct 63 ms 27320 KB Output is correct
6 Correct 82 ms 27232 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 60 ms 26808 KB Output is correct
2 Correct 82 ms 27836 KB Output is correct
3 Correct 83 ms 28040 KB Output is correct
4 Correct 83 ms 28140 KB Output is correct
5 Correct 63 ms 27320 KB Output is correct
6 Correct 82 ms 27232 KB Output is correct
7 Incorrect 107 ms 26756 KB Extra information in the output file
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 58 ms 26792 KB Output is correct
2 Correct 351 ms 48160 KB Output is correct
3 Correct 361 ms 48076 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 58 ms 26792 KB Output is correct
2 Correct 351 ms 48160 KB Output is correct
3 Correct 361 ms 48076 KB Output is correct
4 Incorrect 99 ms 26692 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 54 ms 26916 KB Output is correct
2 Correct 136 ms 56512 KB Output is correct
3 Correct 145 ms 56520 KB Output is correct
4 Correct 145 ms 56612 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 54 ms 26916 KB Output is correct
2 Correct 136 ms 56512 KB Output is correct
3 Correct 145 ms 56520 KB Output is correct
4 Correct 145 ms 56612 KB Output is correct
5 Incorrect 93 ms 26676 KB Extra information in the output file
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 56 ms 26772 KB Output is correct
2 Correct 245 ms 48308 KB Output is correct
3 Correct 172 ms 48544 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 56 ms 26772 KB Output is correct
2 Correct 245 ms 48308 KB Output is correct
3 Correct 172 ms 48544 KB Output is correct
4 Incorrect 98 ms 26780 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 54 ms 26784 KB Output is correct
2 Correct 148 ms 56504 KB Output is correct
3 Correct 144 ms 56704 KB Output is correct
4 Correct 138 ms 56472 KB Output is correct
5 Correct 57 ms 26712 KB Output is correct
6 Correct 236 ms 48196 KB Output is correct
7 Correct 180 ms 48500 KB Output is correct
8 Correct 322 ms 49352 KB Output is correct
9 Correct 265 ms 48968 KB Output is correct
10 Correct 210 ms 53416 KB Output is correct
11 Correct 289 ms 52748 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 54 ms 26784 KB Output is correct
2 Correct 148 ms 56504 KB Output is correct
3 Correct 144 ms 56704 KB Output is correct
4 Correct 138 ms 56472 KB Output is correct
5 Correct 57 ms 26712 KB Output is correct
6 Correct 236 ms 48196 KB Output is correct
7 Correct 180 ms 48500 KB Output is correct
8 Correct 322 ms 49352 KB Output is correct
9 Correct 265 ms 48968 KB Output is correct
10 Correct 210 ms 53416 KB Output is correct
11 Correct 289 ms 52748 KB Output is correct
12 Incorrect 92 ms 26748 KB Extra information in the output file
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 56 ms 26812 KB Output is correct
2 Correct 87 ms 27848 KB Output is correct
3 Correct 82 ms 28068 KB Output is correct
4 Correct 81 ms 27976 KB Output is correct
5 Correct 65 ms 27380 KB Output is correct
6 Correct 88 ms 27228 KB Output is correct
7 Correct 57 ms 26808 KB Output is correct
8 Correct 344 ms 48072 KB Output is correct
9 Correct 340 ms 48056 KB Output is correct
10 Correct 53 ms 26704 KB Output is correct
11 Correct 143 ms 56488 KB Output is correct
12 Correct 140 ms 56468 KB Output is correct
13 Correct 148 ms 56420 KB Output is correct
14 Correct 56 ms 26788 KB Output is correct
15 Correct 228 ms 48256 KB Output is correct
16 Correct 172 ms 48520 KB Output is correct
17 Correct 298 ms 49292 KB Output is correct
18 Correct 240 ms 48944 KB Output is correct
19 Correct 192 ms 53316 KB Output is correct
20 Correct 282 ms 52796 KB Output is correct
21 Correct 331 ms 48024 KB Output is correct
22 Correct 344 ms 48148 KB Output is correct
23 Correct 344 ms 48572 KB Output is correct
24 Correct 331 ms 48524 KB Output is correct
25 Correct 241 ms 50204 KB Output is correct
26 Correct 149 ms 48888 KB Output is correct
27 Correct 150 ms 47980 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 56 ms 26812 KB Output is correct
2 Correct 87 ms 27848 KB Output is correct
3 Correct 82 ms 28068 KB Output is correct
4 Correct 81 ms 27976 KB Output is correct
5 Correct 65 ms 27380 KB Output is correct
6 Correct 88 ms 27228 KB Output is correct
7 Correct 57 ms 26808 KB Output is correct
8 Correct 344 ms 48072 KB Output is correct
9 Correct 340 ms 48056 KB Output is correct
10 Correct 53 ms 26704 KB Output is correct
11 Correct 143 ms 56488 KB Output is correct
12 Correct 140 ms 56468 KB Output is correct
13 Correct 148 ms 56420 KB Output is correct
14 Correct 56 ms 26788 KB Output is correct
15 Correct 228 ms 48256 KB Output is correct
16 Correct 172 ms 48520 KB Output is correct
17 Correct 298 ms 49292 KB Output is correct
18 Correct 240 ms 48944 KB Output is correct
19 Correct 192 ms 53316 KB Output is correct
20 Correct 282 ms 52796 KB Output is correct
21 Correct 331 ms 48024 KB Output is correct
22 Correct 344 ms 48148 KB Output is correct
23 Correct 344 ms 48572 KB Output is correct
24 Correct 331 ms 48524 KB Output is correct
25 Correct 241 ms 50204 KB Output is correct
26 Correct 149 ms 48888 KB Output is correct
27 Correct 150 ms 47980 KB Output is correct
28 Incorrect 99 ms 26772 KB Extra information in the output file
29 Halted 0 ms 0 KB -