oj.uz

Submission #409008

# Submission time Handle Problem Language Result Execution time Memory
409008 2021-05-20T04:06:55 Z balbit Inside information (BOI21_servers) C++14
5 / 100
 917 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) {
    if (dep[a] < dep[b]) swap(a,b);
    a = kth(a, dep[a] - dep[b]);
    if (a == b) return {a,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);
    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!!!!!
    int hoho = HH.t;
    if (a == b) {
        return 1;
    }
    pii lol = LCA(a,b);
    int A = lol.f, B = lol.s;
    int C = A==B?A:par[A];
    int lstedge;

    if (C == b) {
        lstedge = parw[kth(a, dep[a] - dep[C] - 1)];
    }else{
        lstedge = parw[b];
    }
    bug(a,b,hoho,A,B,C,lstedge);
    if (dep[inc[b]] > dep[C] || dep[decr[a]] > dep[C]) {
        return 0;
    }

    if (lstedge > HH.t) {
        return 0;
    }
    if (A!=B) {
        if (parw[A] > parw[B]) {
            return 0;
        }
    }
    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:128:9: warning: unused variable 'hoho' [-Wunused-variable]
  128 |     int hoho = HH.t;
      |         ^~~~
servers.cpp: In function 'int main()':
servers.cpp:238:24: warning: variable 'HH' set but not used [-Wunused-but-set-variable]
  238 |         for (havequery HH : hv) {
      |                        ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 32444 KB Output is correct
2 Correct 57 ms 33160 KB Output is correct
3 Correct 91 ms 37328 KB Output is correct
4 Correct 57 ms 33224 KB Output is correct
5 Correct 57 ms 33488 KB Output is correct
6 Correct 250 ms 73024 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 32444 KB Output is correct
2 Correct 57 ms 33160 KB Output is correct
3 Correct 91 ms 37328 KB Output is correct
4 Correct 57 ms 33224 KB Output is correct
5 Correct 57 ms 33488 KB Output is correct
6 Correct 250 ms 73024 KB Output is correct
7 Correct 56 ms 32304 KB Output is correct
8 Correct 58 ms 34440 KB Output is correct
9 Correct 82 ms 39320 KB Output is correct
10 Correct 65 ms 34448 KB Output is correct
11 Correct 70 ms 34720 KB Output is correct
12 Correct 183 ms 74028 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 32444 KB Output is correct
2 Runtime error 917 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 48 ms 32444 KB Output is correct
2 Runtime error 917 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 48 ms 32416 KB Output is correct
2 Correct 237 ms 65384 KB Output is correct
3 Correct 226 ms 65348 KB Output is correct
4 Runtime error 867 ms 524292 KB Execution killed with signal 9

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 32416 KB Output is correct
2 Correct 237 ms 65384 KB Output is correct
3 Correct 226 ms 65348 KB Output is correct
4 Runtime error 867 ms 524292 KB Execution killed with signal 9

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 32380 KB Output is correct
2 Runtime error 876 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 47 ms 32380 KB Output is correct
2 Runtime error 876 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 48 ms 32380 KB Output is correct
2 Correct 238 ms 65428 KB Output is correct
3 Correct 224 ms 65420 KB Output is correct
4 Runtime error 866 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 48 ms 32380 KB Output is correct
2 Correct 238 ms 65428 KB Output is correct
3 Correct 224 ms 65420 KB Output is correct
4 Runtime error 866 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 47 ms 32368 KB Output is correct
2 Correct 60 ms 33076 KB Output is correct
3 Correct 88 ms 37156 KB Output is correct
4 Correct 57 ms 33236 KB Output is correct
5 Correct 57 ms 33448 KB Output is correct
6 Correct 251 ms 72884 KB Output is correct
7 Correct 50 ms 32476 KB Output is correct
8 Runtime error 897 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 47 ms 32368 KB Output is correct
2 Correct 60 ms 33076 KB Output is correct
3 Correct 88 ms 37156 KB Output is correct
4 Correct 57 ms 33236 KB Output is correct
5 Correct 57 ms 33448 KB Output is correct
6 Correct 251 ms 72884 KB Output is correct
7 Correct 50 ms 32476 KB Output is correct
8 Runtime error 897 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -