oj.uz

Submission #409042

# Submission time Handle Problem Language Result Execution time Memory
409042 2021-05-20T05:56:13 Z balbit Inside information (BOI21_servers) C++14
5 / 100
 941 ms 524292 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];
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};
}

vector<int> here[maxn];
int ans2[maxn];

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;
    }
//    vector<int> pth;
//    vector<int> pth2;
//    while (a != C) {
//        pth.pb(parw[a]);
//        if (par[a] == C) break;
//        a = par[a];
//    }
//    while (b != C) {
//        pth2.pb(parw[b]);
//        if (par[b] == C) break;
//        b = par[b];
//    }
//    if( A!=B) {
////        assert(par[A] == C); assert(par[B] == C);
//        assert(a == A); assert(b==B);
////        assert(parw[A] == pth.back());
////        assert(parw[B] == pth2.back());
//    }
//    while (SZ(pth2)) pth.pb(pth2.back()), pth2.pop_back();
//
//
//
//    REP(i, SZ(pth)) {
//        if (i && pth[i] < pth[i-1]) return 0;
//        if (pth[i] > HH.t) return 0;
//    }
//    return 1;
    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;
    }
    bug(a,b,hoho,A,B,C,lstedge);



    return 1;
}

int nof[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;
    REP(i,q) {
        char c; cin>>c;
        if (c == 'S') {
            int a,b; cin>>a>>b; --a; --b;
            g[a].pb({b,i});
            g[b].pb({a,i});
            E.pb({{a,b},i});
            ans[i] = 202022020;

            {
                vector<int> nw;
                for (int t : here[a]) nw.pb(t);
                for (int t : here[b]) nw.pb(t);
                for (int x : nw) nof[x]++;
                here[a] = here[b] = nw;
            }
        }
        if (c == 'Q') {
            int a, b; cin>>a>>b; --a; --b;
            hv.pb({a,b,i});

            {
                bool fnd = 0;
                for (int t : here[a]) {
                    if (t == b) fnd = 1;
                }
                ans[i] = fnd?-1:-2;
                ans2[i] = fnd?-1:-2;
            }
        }
        if (c == 'C') {
            int a; cin>>a; --a;
            ans[i] = nof[a];
            hey[a].pb(i);
            hey2[a].pb(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);
    if (0){
        for( auto P : E) {
            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() > tm) {
                        ans[hey[v].back()] -= now[v];
    //                    bug("ayy");
                        hey[v].pop_back();
                    }else break;
                }
            }
            int nw = now[a] + now[b];
            now[a] = now[b] = nw;
        }
        REP(i,n) {
            while (!hey[i].empty() ) {
                ans[hey[i].back()] -= now[i];
                hey[i].pop_back();
            }
        }
        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
        }
    }
    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:177:9: warning: unused variable 'hoho' [-Wunused-variable]
  177 |     int hoho = HH.t;
      |         ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 32440 KB Output is correct
2 Correct 89 ms 33120 KB Output is correct
3 Correct 155 ms 37164 KB Output is correct
4 Correct 85 ms 33180 KB Output is correct
5 Correct 68 ms 33528 KB Output is correct
6 Correct 287 ms 72900 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 32440 KB Output is correct
2 Correct 89 ms 33120 KB Output is correct
3 Correct 155 ms 37164 KB Output is correct
4 Correct 85 ms 33180 KB Output is correct
5 Correct 68 ms 33528 KB Output is correct
6 Correct 287 ms 72900 KB Output is correct
7 Correct 59 ms 32296 KB Output is correct
8 Correct 78 ms 33360 KB Output is correct
9 Correct 107 ms 38352 KB Output is correct
10 Correct 74 ms 33376 KB Output is correct
11 Correct 66 ms 33592 KB Output is correct
12 Correct 195 ms 72992 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 32448 KB Output is correct
2 Runtime error 924 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 32448 KB Output is correct
2 Runtime error 924 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32340 KB Output is correct
2 Correct 245 ms 65412 KB Output is correct
3 Correct 255 ms 65396 KB Output is correct
4 Runtime error 907 ms 524292 KB Execution killed with signal 9

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32340 KB Output is correct
2 Correct 245 ms 65412 KB Output is correct
3 Correct 255 ms 65396 KB Output is correct
4 Runtime error 907 ms 524292 KB Execution killed with signal 9

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 32372 KB Output is correct
2 Runtime error 915 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 32372 KB Output is correct
2 Runtime error 915 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32340 KB Output is correct
2 Correct 257 ms 65316 KB Output is correct
3 Correct 243 ms 65424 KB Output is correct
4 Runtime error 878 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32340 KB Output is correct
2 Correct 257 ms 65316 KB Output is correct
3 Correct 243 ms 65424 KB Output is correct
4 Runtime error 878 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 32352 KB Output is correct
2 Correct 90 ms 33184 KB Output is correct
3 Correct 126 ms 37220 KB Output is correct
4 Correct 87 ms 33264 KB Output is correct
5 Correct 71 ms 33484 KB Output is correct
6 Correct 285 ms 72904 KB Output is correct
7 Correct 62 ms 32440 KB Output is correct
8 Runtime error 941 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 32352 KB Output is correct
2 Correct 90 ms 33184 KB Output is correct
3 Correct 126 ms 37220 KB Output is correct
4 Correct 87 ms 33264 KB Output is correct
5 Correct 71 ms 33484 KB Output is correct
6 Correct 285 ms 72904 KB Output is correct
7 Correct 62 ms 32440 KB Output is correct
8 Runtime error 941 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -