oj.uz

Submission #409043

# Submission time Handle Problem Language Result Execution time Memory
409043 2021-05-20T05:56:48 Z balbit Inside information (BOI21_servers) C++14
50 / 100
 355 ms 65216 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;
    }

    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: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 60 ms 31940 KB Output is correct
2 Correct 85 ms 32556 KB Output is correct
3 Correct 84 ms 32668 KB Output is correct
4 Correct 82 ms 32752 KB Output is correct
5 Correct 65 ms 33000 KB Output is correct
6 Correct 91 ms 32756 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 31940 KB Output is correct
2 Correct 85 ms 32556 KB Output is correct
3 Correct 84 ms 32668 KB Output is correct
4 Correct 82 ms 32752 KB Output is correct
5 Correct 65 ms 33000 KB Output is correct
6 Correct 91 ms 32756 KB Output is correct
7 Runtime error 82 ms 63744 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31900 KB Output is correct
2 Correct 335 ms 56796 KB Output is correct
3 Correct 355 ms 56876 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31900 KB Output is correct
2 Correct 335 ms 56796 KB Output is correct
3 Correct 355 ms 56876 KB Output is correct
4 Runtime error 87 ms 63812 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 31964 KB Output is correct
2 Correct 149 ms 64244 KB Output is correct
3 Correct 153 ms 64204 KB Output is correct
4 Correct 152 ms 65176 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 31964 KB Output is correct
2 Correct 149 ms 64244 KB Output is correct
3 Correct 153 ms 64204 KB Output is correct
4 Correct 152 ms 65176 KB Output is correct
5 Runtime error 80 ms 63836 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31940 KB Output is correct
2 Correct 248 ms 57136 KB Output is correct
3 Correct 189 ms 57024 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31940 KB Output is correct
2 Correct 248 ms 57136 KB Output is correct
3 Correct 189 ms 57024 KB Output is correct
4 Runtime error 82 ms 63860 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31920 KB Output is correct
2 Correct 149 ms 64244 KB Output is correct
3 Correct 152 ms 64236 KB Output is correct
4 Correct 146 ms 65216 KB Output is correct
5 Correct 59 ms 32780 KB Output is correct
6 Correct 228 ms 57208 KB Output is correct
7 Correct 192 ms 56948 KB Output is correct
8 Correct 293 ms 58716 KB Output is correct
9 Correct 240 ms 57384 KB Output is correct
10 Correct 193 ms 61828 KB Output is correct
11 Correct 280 ms 61788 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31920 KB Output is correct
2 Correct 149 ms 64244 KB Output is correct
3 Correct 152 ms 64236 KB Output is correct
4 Correct 146 ms 65216 KB Output is correct
5 Correct 59 ms 32780 KB Output is correct
6 Correct 228 ms 57208 KB Output is correct
7 Correct 192 ms 56948 KB Output is correct
8 Correct 293 ms 58716 KB Output is correct
9 Correct 240 ms 57384 KB Output is correct
10 Correct 193 ms 61828 KB Output is correct
11 Correct 280 ms 61788 KB Output is correct
12 Runtime error 79 ms 63776 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 31972 KB Output is correct
2 Correct 85 ms 32548 KB Output is correct
3 Correct 83 ms 32708 KB Output is correct
4 Correct 82 ms 32712 KB Output is correct
5 Correct 64 ms 32996 KB Output is correct
6 Correct 88 ms 32708 KB Output is correct
7 Correct 61 ms 31980 KB Output is correct
8 Correct 340 ms 56444 KB Output is correct
9 Correct 332 ms 56428 KB Output is correct
10 Correct 55 ms 32556 KB Output is correct
11 Correct 156 ms 64872 KB Output is correct
12 Correct 148 ms 64924 KB Output is correct
13 Correct 154 ms 64832 KB Output is correct
14 Correct 68 ms 32544 KB Output is correct
15 Correct 230 ms 57200 KB Output is correct
16 Correct 179 ms 56944 KB Output is correct
17 Correct 304 ms 58744 KB Output is correct
18 Correct 234 ms 57316 KB Output is correct
19 Correct 205 ms 61860 KB Output is correct
20 Correct 287 ms 61812 KB Output is correct
21 Correct 329 ms 56484 KB Output is correct
22 Correct 341 ms 56544 KB Output is correct
23 Correct 334 ms 56828 KB Output is correct
24 Correct 332 ms 56996 KB Output is correct
25 Correct 265 ms 58632 KB Output is correct
26 Correct 165 ms 57440 KB Output is correct
27 Correct 155 ms 56488 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 31972 KB Output is correct
2 Correct 85 ms 32548 KB Output is correct
3 Correct 83 ms 32708 KB Output is correct
4 Correct 82 ms 32712 KB Output is correct
5 Correct 64 ms 32996 KB Output is correct
6 Correct 88 ms 32708 KB Output is correct
7 Correct 61 ms 31980 KB Output is correct
8 Correct 340 ms 56444 KB Output is correct
9 Correct 332 ms 56428 KB Output is correct
10 Correct 55 ms 32556 KB Output is correct
11 Correct 156 ms 64872 KB Output is correct
12 Correct 148 ms 64924 KB Output is correct
13 Correct 154 ms 64832 KB Output is correct
14 Correct 68 ms 32544 KB Output is correct
15 Correct 230 ms 57200 KB Output is correct
16 Correct 179 ms 56944 KB Output is correct
17 Correct 304 ms 58744 KB Output is correct
18 Correct 234 ms 57316 KB Output is correct
19 Correct 205 ms 61860 KB Output is correct
20 Correct 287 ms 61812 KB Output is correct
21 Correct 329 ms 56484 KB Output is correct
22 Correct 341 ms 56544 KB Output is correct
23 Correct 334 ms 56828 KB Output is correct
24 Correct 332 ms 56996 KB Output is correct
25 Correct 265 ms 58632 KB Output is correct
26 Correct 165 ms 57440 KB Output is correct
27 Correct 155 ms 56488 KB Output is correct
28 Runtime error 86 ms 63844 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -