oj.uz

Submission #409054

# Submission time Handle Problem Language Result Execution time Memory
409054 2021-05-20T06:37:21 Z balbit Inside information (BOI21_servers) C++14
50 / 100
 1712 ms 56616 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];
    }

    {
        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;
      |         ^~~~
servers.cpp: In function 'int main()':
servers.cpp:215:17: warning: unused variable 'tm' [-Wunused-variable]
  215 |             int tm = P.s;
      |                 ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 126 ms 26808 KB Output is correct
2 Correct 167 ms 27840 KB Output is correct
3 Correct 171 ms 28096 KB Output is correct
4 Correct 162 ms 27996 KB Output is correct
5 Correct 151 ms 27368 KB Output is correct
6 Correct 175 ms 27344 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 126 ms 26808 KB Output is correct
2 Correct 167 ms 27840 KB Output is correct
3 Correct 171 ms 28096 KB Output is correct
4 Correct 162 ms 27996 KB Output is correct
5 Correct 151 ms 27368 KB Output is correct
6 Correct 175 ms 27344 KB Output is correct
7 Incorrect 134 ms 26692 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 126 ms 26772 KB Output is correct
2 Correct 1390 ms 48048 KB Output is correct
3 Correct 1403 ms 47960 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 126 ms 26772 KB Output is correct
2 Correct 1390 ms 48048 KB Output is correct
3 Correct 1403 ms 47960 KB Output is correct
4 Incorrect 140 ms 26708 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 123 ms 26816 KB Output is correct
2 Correct 1215 ms 56484 KB Output is correct
3 Correct 1237 ms 56496 KB Output is correct
4 Correct 859 ms 56524 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 26816 KB Output is correct
2 Correct 1215 ms 56484 KB Output is correct
3 Correct 1237 ms 56496 KB Output is correct
4 Correct 859 ms 56524 KB Output is correct
5 Incorrect 126 ms 26784 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 127 ms 26824 KB Output is correct
2 Correct 1062 ms 48320 KB Output is correct
3 Correct 1424 ms 48628 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 26824 KB Output is correct
2 Correct 1062 ms 48320 KB Output is correct
3 Correct 1424 ms 48628 KB Output is correct
4 Incorrect 134 ms 26672 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 126 ms 26936 KB Output is correct
2 Correct 1273 ms 56500 KB Output is correct
3 Correct 1229 ms 56616 KB Output is correct
4 Correct 882 ms 56488 KB Output is correct
5 Correct 132 ms 26928 KB Output is correct
6 Correct 1027 ms 48376 KB Output is correct
7 Correct 1442 ms 48628 KB Output is correct
8 Correct 1712 ms 49324 KB Output is correct
9 Correct 1391 ms 48944 KB Output is correct
10 Correct 1255 ms 53420 KB Output is correct
11 Correct 1551 ms 52852 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 126 ms 26936 KB Output is correct
2 Correct 1273 ms 56500 KB Output is correct
3 Correct 1229 ms 56616 KB Output is correct
4 Correct 882 ms 56488 KB Output is correct
5 Correct 132 ms 26928 KB Output is correct
6 Correct 1027 ms 48376 KB Output is correct
7 Correct 1442 ms 48628 KB Output is correct
8 Correct 1712 ms 49324 KB Output is correct
9 Correct 1391 ms 48944 KB Output is correct
10 Correct 1255 ms 53420 KB Output is correct
11 Correct 1551 ms 52852 KB Output is correct
12 Incorrect 126 ms 26740 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 127 ms 26800 KB Output is correct
2 Correct 166 ms 27832 KB Output is correct
3 Correct 167 ms 28088 KB Output is correct
4 Correct 168 ms 28132 KB Output is correct
5 Correct 150 ms 27356 KB Output is correct
6 Correct 176 ms 27324 KB Output is correct
7 Correct 133 ms 26848 KB Output is correct
8 Correct 1465 ms 48048 KB Output is correct
9 Correct 1393 ms 48064 KB Output is correct
10 Correct 125 ms 26792 KB Output is correct
11 Correct 1225 ms 56492 KB Output is correct
12 Correct 1216 ms 56528 KB Output is correct
13 Correct 871 ms 56492 KB Output is correct
14 Correct 125 ms 26804 KB Output is correct
15 Correct 1076 ms 48316 KB Output is correct
16 Correct 1474 ms 48516 KB Output is correct
17 Correct 1667 ms 49292 KB Output is correct
18 Correct 1440 ms 48952 KB Output is correct
19 Correct 1346 ms 53356 KB Output is correct
20 Correct 1597 ms 52804 KB Output is correct
21 Correct 1470 ms 48060 KB Output is correct
22 Correct 1572 ms 48148 KB Output is correct
23 Correct 1481 ms 48532 KB Output is correct
24 Correct 1509 ms 48544 KB Output is correct
25 Correct 1455 ms 50244 KB Output is correct
26 Correct 1535 ms 48908 KB Output is correct
27 Correct 1661 ms 47956 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 127 ms 26800 KB Output is correct
2 Correct 166 ms 27832 KB Output is correct
3 Correct 167 ms 28088 KB Output is correct
4 Correct 168 ms 28132 KB Output is correct
5 Correct 150 ms 27356 KB Output is correct
6 Correct 176 ms 27324 KB Output is correct
7 Correct 133 ms 26848 KB Output is correct
8 Correct 1465 ms 48048 KB Output is correct
9 Correct 1393 ms 48064 KB Output is correct
10 Correct 125 ms 26792 KB Output is correct
11 Correct 1225 ms 56492 KB Output is correct
12 Correct 1216 ms 56528 KB Output is correct
13 Correct 871 ms 56492 KB Output is correct
14 Correct 125 ms 26804 KB Output is correct
15 Correct 1076 ms 48316 KB Output is correct
16 Correct 1474 ms 48516 KB Output is correct
17 Correct 1667 ms 49292 KB Output is correct
18 Correct 1440 ms 48952 KB Output is correct
19 Correct 1346 ms 53356 KB Output is correct
20 Correct 1597 ms 52804 KB Output is correct
21 Correct 1470 ms 48060 KB Output is correct
22 Correct 1572 ms 48148 KB Output is correct
23 Correct 1481 ms 48532 KB Output is correct
24 Correct 1509 ms 48544 KB Output is correct
25 Correct 1455 ms 50244 KB Output is correct
26 Correct 1535 ms 48908 KB Output is correct
27 Correct 1661 ms 47956 KB Output is correct
28 Incorrect 139 ms 26696 KB Extra information in the output file
29 Halted 0 ms 0 KB -