oj.uz

Submission #409034

# Submission time Handle Problem Language Result Execution time Memory
409034 2021-05-20T05:43:18 Z balbit Inside information (BOI21_servers) C++14
5 / 100
 947 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!!!!!

    pii lol = LCA(a,b);
    int A = lol.f, B = lol.s;
    int C = A==B?A:par[A];

    vector<int> pth;
    vector<int> pth2;
    while (a != C) {
        pth.pb(parw[a]);
        a = par[a];
    }
    while (b != C) {
        pth2.pb(parw[b]);
        b = par[b];
    }
    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;

    int hoho = HH.t;
    if (a == b) {
        return 1;
    }
    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:151:9: warning: unused variable 'hoho' [-Wunused-variable]
  151 |     int hoho = HH.t;
      |         ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 87 ms 32948 KB Output is correct
2 Correct 147 ms 33548 KB Output is correct
3 Correct 136 ms 37684 KB Output is correct
4 Correct 761 ms 33736 KB Output is correct
5 Correct 914 ms 33952 KB Output is correct
6 Correct 309 ms 73276 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 87 ms 32948 KB Output is correct
2 Correct 147 ms 33548 KB Output is correct
3 Correct 136 ms 37684 KB Output is correct
4 Correct 761 ms 33736 KB Output is correct
5 Correct 914 ms 33952 KB Output is correct
6 Correct 309 ms 73276 KB Output is correct
7 Correct 83 ms 32468 KB Output is correct
8 Correct 111 ms 33776 KB Output is correct
9 Correct 110 ms 38648 KB Output is correct
10 Correct 396 ms 33844 KB Output is correct
11 Correct 492 ms 34008 KB Output is correct
12 Correct 203 ms 73384 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 32984 KB Output is correct
2 Runtime error 921 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 72 ms 32984 KB Output is correct
2 Runtime error 921 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 93 ms 32960 KB Output is correct
2 Correct 282 ms 67076 KB Output is correct
3 Correct 285 ms 66920 KB Output is correct
4 Runtime error 883 ms 524292 KB Execution killed with signal 9

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 32960 KB Output is correct
2 Correct 282 ms 67076 KB Output is correct
3 Correct 285 ms 66920 KB Output is correct
4 Runtime error 883 ms 524292 KB Execution killed with signal 9

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 32856 KB Output is correct
2 Runtime error 889 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 87 ms 32856 KB Output is correct
2 Runtime error 889 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 99 ms 32984 KB Output is correct
2 Correct 301 ms 66972 KB Output is correct
3 Correct 261 ms 67016 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 99 ms 32984 KB Output is correct
2 Correct 301 ms 66972 KB Output is correct
3 Correct 261 ms 67016 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 87 ms 33008 KB Output is correct
2 Correct 148 ms 33480 KB Output is correct
3 Correct 142 ms 37616 KB Output is correct
4 Correct 740 ms 33616 KB Output is correct
5 Correct 947 ms 33836 KB Output is correct
6 Correct 295 ms 73364 KB Output is correct
7 Correct 88 ms 32824 KB Output is correct
8 Runtime error 923 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 87 ms 33008 KB Output is correct
2 Correct 148 ms 33480 KB Output is correct
3 Correct 142 ms 37616 KB Output is correct
4 Correct 740 ms 33616 KB Output is correct
5 Correct 947 ms 33836 KB Output is correct
6 Correct 295 ms 73364 KB Output is correct
7 Correct 88 ms 32824 KB Output is correct
8 Runtime error 923 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -