oj.uz

Submission #409062

# Submission time Handle Problem Language Result Execution time Memory
409062 2021-05-20T06:44:15 Z balbit Inside information (BOI21_servers) C++14
50 / 100
 349 ms 56624 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;
    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;
    if (a == b) {
        return 1;
    }
    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) {
        ans[p.s] = 1;
        int v = p.f; int ansi = p.s;
        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:147:9: warning: unused variable 'hoho' [-Wunused-variable]
  147 |     int hoho = HH.t;
      |         ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26804 KB Output is correct
2 Correct 83 ms 27852 KB Output is correct
3 Correct 82 ms 28084 KB Output is correct
4 Correct 81 ms 27968 KB Output is correct
5 Correct 63 ms 27264 KB Output is correct
6 Correct 83 ms 27272 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26804 KB Output is correct
2 Correct 83 ms 27852 KB Output is correct
3 Correct 82 ms 28084 KB Output is correct
4 Correct 81 ms 27968 KB Output is correct
5 Correct 63 ms 27264 KB Output is correct
6 Correct 83 ms 27272 KB Output is correct
7 Incorrect 102 ms 26672 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26728 KB Output is correct
2 Correct 345 ms 48052 KB Output is correct
3 Correct 330 ms 48032 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26728 KB Output is correct
2 Correct 345 ms 48052 KB Output is correct
3 Correct 330 ms 48032 KB Output is correct
4 Incorrect 98 ms 26788 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26780 KB Output is correct
2 Correct 147 ms 56620 KB Output is correct
3 Correct 145 ms 56424 KB Output is correct
4 Correct 141 ms 56412 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26780 KB Output is correct
2 Correct 147 ms 56620 KB Output is correct
3 Correct 145 ms 56424 KB Output is correct
4 Correct 141 ms 56412 KB Output is correct
5 Incorrect 94 ms 26684 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26744 KB Output is correct
2 Correct 252 ms 48312 KB Output is correct
3 Correct 184 ms 48536 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26744 KB Output is correct
2 Correct 252 ms 48312 KB Output is correct
3 Correct 184 ms 48536 KB Output is correct
4 Incorrect 99 ms 26668 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26804 KB Output is correct
2 Correct 149 ms 56624 KB Output is correct
3 Correct 151 ms 56528 KB Output is correct
4 Correct 140 ms 56512 KB Output is correct
5 Correct 57 ms 26732 KB Output is correct
6 Correct 234 ms 48248 KB Output is correct
7 Correct 175 ms 48516 KB Output is correct
8 Correct 292 ms 49228 KB Output is correct
9 Correct 240 ms 48972 KB Output is correct
10 Correct 205 ms 53440 KB Output is correct
11 Correct 305 ms 52820 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 26804 KB Output is correct
2 Correct 149 ms 56624 KB Output is correct
3 Correct 151 ms 56528 KB Output is correct
4 Correct 140 ms 56512 KB Output is correct
5 Correct 57 ms 26732 KB Output is correct
6 Correct 234 ms 48248 KB Output is correct
7 Correct 175 ms 48516 KB Output is correct
8 Correct 292 ms 49228 KB Output is correct
9 Correct 240 ms 48972 KB Output is correct
10 Correct 205 ms 53440 KB Output is correct
11 Correct 305 ms 52820 KB Output is correct
12 Incorrect 93 ms 26752 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 26784 KB Output is correct
2 Correct 83 ms 27868 KB Output is correct
3 Correct 81 ms 28056 KB Output is correct
4 Correct 82 ms 27976 KB Output is correct
5 Correct 62 ms 27264 KB Output is correct
6 Correct 84 ms 27256 KB Output is correct
7 Correct 57 ms 26808 KB Output is correct
8 Correct 340 ms 48000 KB Output is correct
9 Correct 349 ms 48032 KB Output is correct
10 Correct 52 ms 26772 KB Output is correct
11 Correct 144 ms 56612 KB Output is correct
12 Correct 144 ms 56548 KB Output is correct
13 Correct 146 ms 56492 KB Output is correct
14 Correct 57 ms 26740 KB Output is correct
15 Correct 235 ms 48316 KB Output is correct
16 Correct 177 ms 48528 KB Output is correct
17 Correct 294 ms 49264 KB Output is correct
18 Correct 252 ms 49072 KB Output is correct
19 Correct 203 ms 53444 KB Output is correct
20 Correct 290 ms 52780 KB Output is correct
21 Correct 333 ms 48036 KB Output is correct
22 Correct 343 ms 48240 KB Output is correct
23 Correct 321 ms 48452 KB Output is correct
24 Correct 344 ms 48528 KB Output is correct
25 Correct 277 ms 50228 KB Output is correct
26 Correct 156 ms 48884 KB Output is correct
27 Correct 144 ms 47908 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 26784 KB Output is correct
2 Correct 83 ms 27868 KB Output is correct
3 Correct 81 ms 28056 KB Output is correct
4 Correct 82 ms 27976 KB Output is correct
5 Correct 62 ms 27264 KB Output is correct
6 Correct 84 ms 27256 KB Output is correct
7 Correct 57 ms 26808 KB Output is correct
8 Correct 340 ms 48000 KB Output is correct
9 Correct 349 ms 48032 KB Output is correct
10 Correct 52 ms 26772 KB Output is correct
11 Correct 144 ms 56612 KB Output is correct
12 Correct 144 ms 56548 KB Output is correct
13 Correct 146 ms 56492 KB Output is correct
14 Correct 57 ms 26740 KB Output is correct
15 Correct 235 ms 48316 KB Output is correct
16 Correct 177 ms 48528 KB Output is correct
17 Correct 294 ms 49264 KB Output is correct
18 Correct 252 ms 49072 KB Output is correct
19 Correct 203 ms 53444 KB Output is correct
20 Correct 290 ms 52780 KB Output is correct
21 Correct 333 ms 48036 KB Output is correct
22 Correct 343 ms 48240 KB Output is correct
23 Correct 321 ms 48452 KB Output is correct
24 Correct 344 ms 48528 KB Output is correct
25 Correct 277 ms 50228 KB Output is correct
26 Correct 156 ms 48884 KB Output is correct
27 Correct 144 ms 47908 KB Output is correct
28 Incorrect 100 ms 26692 KB Extra information in the output file
29 Halted 0 ms 0 KB -