oj.uz

Submission #409059

# Submission time Handle Problem Language Result Execution time Memory
409059 2021-05-20T06:42:17 Z balbit Inside information (BOI21_servers) C++14
50 / 100
 363 ms 56580 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 = 200;
    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;
        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 66 ms 26808 KB Output is correct
2 Correct 84 ms 27900 KB Output is correct
3 Correct 80 ms 28100 KB Output is correct
4 Correct 82 ms 27976 KB Output is correct
5 Correct 62 ms 27356 KB Output is correct
6 Correct 85 ms 27312 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 26808 KB Output is correct
2 Correct 84 ms 27900 KB Output is correct
3 Correct 80 ms 28100 KB Output is correct
4 Correct 82 ms 27976 KB Output is correct
5 Correct 62 ms 27356 KB Output is correct
6 Correct 85 ms 27312 KB Output is correct
7 Runtime error 94 ms 53340 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26744 KB Output is correct
2 Correct 361 ms 48076 KB Output is correct
3 Correct 363 ms 48148 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26744 KB Output is correct
2 Correct 361 ms 48076 KB Output is correct
3 Correct 363 ms 48148 KB Output is correct
4 Runtime error 85 ms 53340 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 26756 KB Output is correct
2 Correct 155 ms 56512 KB Output is correct
3 Correct 148 ms 56416 KB Output is correct
4 Correct 141 ms 56580 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 26756 KB Output is correct
2 Correct 155 ms 56512 KB Output is correct
3 Correct 148 ms 56416 KB Output is correct
4 Correct 141 ms 56580 KB Output is correct
5 Runtime error 78 ms 53376 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26740 KB Output is correct
2 Correct 244 ms 48264 KB Output is correct
3 Correct 179 ms 48488 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26740 KB Output is correct
2 Correct 244 ms 48264 KB Output is correct
3 Correct 179 ms 48488 KB Output is correct
4 Runtime error 83 ms 53320 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 26820 KB Output is correct
2 Correct 157 ms 56452 KB Output is correct
3 Correct 142 ms 56496 KB Output is correct
4 Correct 147 ms 56528 KB Output is correct
5 Correct 59 ms 26800 KB Output is correct
6 Correct 232 ms 48296 KB Output is correct
7 Correct 185 ms 48564 KB Output is correct
8 Correct 300 ms 49284 KB Output is correct
9 Correct 238 ms 48936 KB Output is correct
10 Correct 234 ms 53372 KB Output is correct
11 Correct 285 ms 52812 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 26820 KB Output is correct
2 Correct 157 ms 56452 KB Output is correct
3 Correct 142 ms 56496 KB Output is correct
4 Correct 147 ms 56528 KB Output is correct
5 Correct 59 ms 26800 KB Output is correct
6 Correct 232 ms 48296 KB Output is correct
7 Correct 185 ms 48564 KB Output is correct
8 Correct 300 ms 49284 KB Output is correct
9 Correct 238 ms 48936 KB Output is correct
10 Correct 234 ms 53372 KB Output is correct
11 Correct 285 ms 52812 KB Output is correct
12 Runtime error 79 ms 53372 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 26812 KB Output is correct
2 Correct 85 ms 27856 KB Output is correct
3 Correct 84 ms 28096 KB Output is correct
4 Correct 83 ms 27964 KB Output is correct
5 Correct 64 ms 27312 KB Output is correct
6 Correct 84 ms 27264 KB Output is correct
7 Correct 59 ms 26804 KB Output is correct
8 Correct 350 ms 47964 KB Output is correct
9 Correct 363 ms 48024 KB Output is correct
10 Correct 60 ms 26740 KB Output is correct
11 Correct 143 ms 56496 KB Output is correct
12 Correct 142 ms 56460 KB Output is correct
13 Correct 152 ms 56460 KB Output is correct
14 Correct 57 ms 26784 KB Output is correct
15 Correct 265 ms 48368 KB Output is correct
16 Correct 180 ms 48548 KB Output is correct
17 Correct 291 ms 49244 KB Output is correct
18 Correct 256 ms 48964 KB Output is correct
19 Correct 203 ms 53384 KB Output is correct
20 Correct 306 ms 52892 KB Output is correct
21 Correct 331 ms 48060 KB Output is correct
22 Correct 334 ms 48152 KB Output is correct
23 Correct 320 ms 48420 KB Output is correct
24 Correct 345 ms 48548 KB Output is correct
25 Correct 253 ms 50344 KB Output is correct
26 Correct 164 ms 48888 KB Output is correct
27 Correct 146 ms 47948 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 26812 KB Output is correct
2 Correct 85 ms 27856 KB Output is correct
3 Correct 84 ms 28096 KB Output is correct
4 Correct 83 ms 27964 KB Output is correct
5 Correct 64 ms 27312 KB Output is correct
6 Correct 84 ms 27264 KB Output is correct
7 Correct 59 ms 26804 KB Output is correct
8 Correct 350 ms 47964 KB Output is correct
9 Correct 363 ms 48024 KB Output is correct
10 Correct 60 ms 26740 KB Output is correct
11 Correct 143 ms 56496 KB Output is correct
12 Correct 142 ms 56460 KB Output is correct
13 Correct 152 ms 56460 KB Output is correct
14 Correct 57 ms 26784 KB Output is correct
15 Correct 265 ms 48368 KB Output is correct
16 Correct 180 ms 48548 KB Output is correct
17 Correct 291 ms 49244 KB Output is correct
18 Correct 256 ms 48964 KB Output is correct
19 Correct 203 ms 53384 KB Output is correct
20 Correct 306 ms 52892 KB Output is correct
21 Correct 331 ms 48060 KB Output is correct
22 Correct 334 ms 48152 KB Output is correct
23 Correct 320 ms 48420 KB Output is correct
24 Correct 345 ms 48548 KB Output is correct
25 Correct 253 ms 50344 KB Output is correct
26 Correct 164 ms 48888 KB Output is correct
27 Correct 146 ms 47948 KB Output is correct
28 Runtime error 85 ms 53360 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -