oj.uz

Submission #409037

# Submission time Handle Problem Language Result Execution time Memory
409037 2021-05-20T05:46:24 Z balbit Inside information (BOI21_servers) C++14
5 / 100
 1006 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();
    if (dep[inc[b]] > dep[C] || dep[decr[a]] > dep[C]) {
        return 0;
    }
    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) {
        int thon = kth(a, dep[a] - dep[C] - 1);
        assert(par[thon] == C);
        lstedge = parw[thon];
    }else{
        lstedge = parw[b];
    }
    bug(a,b,hoho,A,B,C,lstedge);


    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:153:9: warning: unused variable 'hoho' [-Wunused-variable]
  153 |     int hoho = HH.t;
      |         ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32440 KB Output is correct
2 Correct 142 ms 33096 KB Output is correct
3 Correct 138 ms 37232 KB Output is correct
4 Correct 731 ms 33236 KB Output is correct
5 Correct 921 ms 33452 KB Output is correct
6 Correct 305 ms 72816 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32440 KB Output is correct
2 Correct 142 ms 33096 KB Output is correct
3 Correct 138 ms 37232 KB Output is correct
4 Correct 731 ms 33236 KB Output is correct
5 Correct 921 ms 33452 KB Output is correct
6 Correct 305 ms 72816 KB Output is correct
7 Correct 86 ms 32264 KB Output is correct
8 Correct 149 ms 33276 KB Output is correct
9 Correct 108 ms 38252 KB Output is correct
10 Correct 395 ms 33512 KB Output is correct
11 Correct 534 ms 33720 KB Output is correct
12 Correct 215 ms 72992 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 32400 KB Output is correct
2 Runtime error 1006 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 32400 KB Output is correct
2 Runtime error 1006 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 141 ms 32392 KB Output is correct
2 Correct 275 ms 66228 KB Output is correct
3 Correct 263 ms 66172 KB Output is correct
4 Runtime error 923 ms 524292 KB Execution killed with signal 9

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 32392 KB Output is correct
2 Correct 275 ms 66228 KB Output is correct
3 Correct 263 ms 66172 KB Output is correct
4 Runtime error 923 ms 524292 KB Execution killed with signal 9

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 32336 KB Output is correct
2 Runtime error 942 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 98 ms 32336 KB Output is correct
2 Runtime error 942 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 97 ms 32348 KB Output is correct
2 Correct 276 ms 66172 KB Output is correct
3 Correct 265 ms 66212 KB Output is correct
4 Runtime error 895 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 97 ms 32348 KB Output is correct
2 Correct 276 ms 66172 KB Output is correct
3 Correct 265 ms 66212 KB Output is correct
4 Runtime error 895 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 90 ms 32344 KB Output is correct
2 Correct 176 ms 33096 KB Output is correct
3 Correct 141 ms 37236 KB Output is correct
4 Correct 740 ms 33236 KB Output is correct
5 Correct 918 ms 33448 KB Output is correct
6 Correct 301 ms 72952 KB Output is correct
7 Correct 76 ms 32444 KB Output is correct
8 Runtime error 947 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 90 ms 32344 KB Output is correct
2 Correct 176 ms 33096 KB Output is correct
3 Correct 141 ms 37236 KB Output is correct
4 Correct 740 ms 33236 KB Output is correct
5 Correct 918 ms 33448 KB Output is correct
6 Correct 301 ms 72952 KB Output is correct
7 Correct 76 ms 32444 KB Output is correct
8 Runtime error 947 ms 524292 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -