oj.uz

Submission #409041

# Submission time Handle Problem Language Result Execution time Memory
409041 2021-05-20T05:53:54 Z balbit Inside information (BOI21_servers) C++14
5 / 100
 958 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};
    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);
    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]);
        a = par[a];
    }
    while (b != C) {
        pth2.pb(parw[b]);
        b = par[b];
    }
    if( A!=B) {
        assert(par[A] == C); assert(par[B] == C);
//        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:170:9: warning: unused variable 'hoho' [-Wunused-variable]
  170 |     int hoho = HH.t;
      |         ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 32412 KB Output is correct
2 Correct 87 ms 33100 KB Output is correct
3 Correct 131 ms 37240 KB Output is correct
4 Correct 85 ms 33224 KB Output is correct
5 Correct 71 ms 33448 KB Output is correct
6 Correct 296 ms 72864 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 32412 KB Output is correct
2 Correct 87 ms 33100 KB Output is correct
3 Correct 131 ms 37240 KB Output is correct
4 Correct 85 ms 33224 KB Output is correct
5 Correct 71 ms 33448 KB Output is correct
6 Correct 296 ms 72864 KB Output is correct
7 Correct 67 ms 32320 KB Output is correct
8 Correct 75 ms 33288 KB Output is correct
9 Correct 105 ms 38372 KB Output is correct
10 Correct 76 ms 33380 KB Output is correct
11 Correct 67 ms 33508 KB Output is correct
12 Correct 202 ms 72988 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 32472 KB Output is correct
2 Runtime error 935 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 74 ms 32472 KB Output is correct
2 Runtime error 935 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 32448 KB Output is correct
2 Correct 242 ms 65376 KB Output is correct
3 Correct 240 ms 65316 KB Output is correct
4 Runtime error 902 ms 524292 KB Execution killed with signal 9

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 32448 KB Output is correct
2 Correct 242 ms 65376 KB Output is correct
3 Correct 240 ms 65316 KB Output is correct
4 Runtime error 902 ms 524292 KB Execution killed with signal 9

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 32360 KB Output is correct
2 Runtime error 908 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 61 ms 32360 KB Output is correct
2 Runtime error 908 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 54 ms 32420 KB Output is correct
2 Correct 249 ms 65336 KB Output is correct
3 Correct 251 ms 65404 KB Output is correct
4 Runtime error 889 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 54 ms 32420 KB Output is correct
2 Correct 249 ms 65336 KB Output is correct
3 Correct 251 ms 65404 KB Output is correct
4 Runtime error 889 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 65 ms 32444 KB Output is correct
2 Correct 92 ms 33200 KB Output is correct
3 Correct 159 ms 37244 KB Output is correct
4 Correct 94 ms 33320 KB Output is correct
5 Correct 69 ms 33540 KB Output is correct
6 Correct 295 ms 73056 KB Output is correct
7 Correct 72 ms 32464 KB Output is correct
8 Runtime error 958 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 65 ms 32444 KB Output is correct
2 Correct 92 ms 33200 KB Output is correct
3 Correct 159 ms 37244 KB Output is correct
4 Correct 94 ms 33320 KB Output is correct
5 Correct 69 ms 33540 KB Output is correct
6 Correct 295 ms 73056 KB Output is correct
7 Correct 72 ms 32464 KB Output is correct
8 Runtime error 958 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -