oj.uz

Submission #409072

# Submission time Handle Problem Language Result Execution time Memory
409072 2021-05-20T06:57:14 Z balbit Inside information (BOI21_servers) C++14
52.5 / 100
 3500 ms 58800 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*2];
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};
}


bool yes(havequery HH){
    int a = HH.a, b = HH.b;
    if (a == b) {
        return 1;
    }
    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;
    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;
    }

    return 1;
}

int pa[maxn], pb[maxn];
bool isedge[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;
    vector<pii> hmm;
    REP(i,q) {
        char c; cin>>c;
        if (c == 'S') {
            int a,b; cin>>a>>b; --a; --b;
            pa[i] = a; pb[i] =b; isedge[i] = 1;
            g[a].pb({b,i});
            g[b].pb({a,i});
            E.pb({{a,b},i});
            ans[i] = 202022020;

        }
        if (c == 'Q') {
            int a, b; cin>>a>>b; --a; --b;
            hv.pb({a,b,i});

        }
        if (c == 'C') {
            int a; cin>>a; --a;
//            ans[i] = nof[a];
            hey[a].pb(i);
            hey2[a].pb(i);
            hmm.pb({a,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);
    const int BS = 300;
    int start = 0; while (start + BS<=q) start += BS;
    bug(start);
    for (int T = start; T >=0; T-=BS){

        fill(now, now+maxn, 1);
        for( auto P : E) {
            if (P.s >= T) continue;
            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() >= T-1) {
                        ans[hey[v].back()] -= now[v];
                        hey[v].pop_back();
                    }else break;
                }
            }
            int nw = now[a] + now[b];
            now[a] = now[b] = nw;
        }
        REP(i,n) {
            while (!hey[i].empty() ) {
                if (hey[i].back() >= T-1) {
                    ans[hey[i].back()] -= now[i];
                    hey[i].pop_back();
                }else break;
            }
        }

        REP(i,n) {
            while (!hey2[i].empty()) {
                if (hey2[i].back() >= T-1){
                    ans[hey2[i].back()] += 1 + now[i];
                    hey2[i].pop_back();
                }
                else break;
            }
        }
    }
//    fill(now, now+maxn, 1);

    {
        for (havequery HH : hv) {
//            continue;
            ans[HH.t] = yes(HH)?-1:-2;
            // is the path from a
        }
    }
    for (pii p : hmm) {
        int v = p.f; int ansi = p.s;
//        ans[ansi] = 1;
//        REP(i,n) ans[ansi] += yes({i,v,ansi});
//        continue;
        int tk = 0;
        while (tk -1 <= ansi) tk += BS;
        tk -= BS;

        for (int i = tk; i <= ansi; ++i) {
            bug(i, ansi);
            if (!isedge[i]) continue;
            int a = pa[i], b= pb[i];
            if (dep[a] > dep[b]) swap(a,b);
            if (ispar(b,v)) {
                swap(a,b);
            }
            // i want b!
            ans[ansi] += yes({b,v,ansi});
        }
    }
    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:150:9: warning: unused variable 'hoho' [-Wunused-variable]
  150 |     int hoho = HH.t;
      |         ^~~~
servers.cpp: In function 'int main()':
servers.cpp:215:17: warning: unused variable 'tm' [-Wunused-variable]
  215 |             int tm = P.s;
      |                 ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 26788 KB Output is correct
2 Correct 147 ms 27860 KB Output is correct
3 Correct 143 ms 27988 KB Output is correct
4 Correct 139 ms 27984 KB Output is correct
5 Correct 134 ms 27324 KB Output is correct
6 Correct 150 ms 27236 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 26788 KB Output is correct
2 Correct 147 ms 27860 KB Output is correct
3 Correct 143 ms 27988 KB Output is correct
4 Correct 139 ms 27984 KB Output is correct
5 Correct 134 ms 27324 KB Output is correct
6 Correct 150 ms 27236 KB Output is correct
7 Correct 112 ms 26676 KB Output is correct
8 Correct 253 ms 28544 KB Output is correct
9 Correct 172 ms 28484 KB Output is correct
10 Correct 240 ms 28660 KB Output is correct
11 Correct 173 ms 27960 KB Output is correct
12 Correct 214 ms 27776 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 104 ms 26780 KB Output is correct
2 Correct 1511 ms 48032 KB Output is correct
3 Correct 1448 ms 48052 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 104 ms 26780 KB Output is correct
2 Correct 1511 ms 48032 KB Output is correct
3 Correct 1448 ms 48052 KB Output is correct
4 Correct 109 ms 26736 KB Output is correct
5 Correct 3198 ms 48236 KB Output is correct
6 Correct 2472 ms 48784 KB Output is correct
7 Execution timed out 3582 ms 48124 KB Time limit exceeded

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 26828 KB Output is correct
2 Correct 1148 ms 56492 KB Output is correct
3 Correct 1302 ms 56492 KB Output is correct
4 Correct 813 ms 56604 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 26828 KB Output is correct
2 Correct 1148 ms 56492 KB Output is correct
3 Correct 1302 ms 56492 KB Output is correct
4 Correct 813 ms 56604 KB Output is correct
5 Correct 103 ms 26720 KB Output is correct
6 Execution timed out 3565 ms 58800 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 26808 KB Output is correct
2 Correct 1075 ms 48316 KB Output is correct
3 Correct 1775 ms 48512 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 26808 KB Output is correct
2 Correct 1075 ms 48316 KB Output is correct
3 Correct 1775 ms 48512 KB Output is correct
4 Correct 105 ms 26700 KB Output is correct
5 Correct 3216 ms 50268 KB Output is correct
6 Execution timed out 3561 ms 51156 KB Time limit exceeded

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 98 ms 26736 KB Output is correct
2 Correct 1205 ms 56488 KB Output is correct
3 Correct 1137 ms 56488 KB Output is correct
4 Correct 903 ms 56488 KB Output is correct
5 Correct 110 ms 26808 KB Output is correct
6 Correct 1010 ms 48324 KB Output is correct
7 Correct 1456 ms 48644 KB Output is correct
8 Correct 1567 ms 49252 KB Output is correct
9 Correct 1414 ms 48948 KB Output is correct
10 Correct 1243 ms 53376 KB Output is correct
11 Correct 1594 ms 52724 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 98 ms 26736 KB Output is correct
2 Correct 1205 ms 56488 KB Output is correct
3 Correct 1137 ms 56488 KB Output is correct
4 Correct 903 ms 56488 KB Output is correct
5 Correct 110 ms 26808 KB Output is correct
6 Correct 1010 ms 48324 KB Output is correct
7 Correct 1456 ms 48644 KB Output is correct
8 Correct 1567 ms 49252 KB Output is correct
9 Correct 1414 ms 48948 KB Output is correct
10 Correct 1243 ms 53376 KB Output is correct
11 Correct 1594 ms 52724 KB Output is correct
12 Correct 101 ms 26696 KB Output is correct
13 Execution timed out 3533 ms 58732 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 26808 KB Output is correct
2 Correct 144 ms 27860 KB Output is correct
3 Correct 142 ms 27984 KB Output is correct
4 Correct 139 ms 27996 KB Output is correct
5 Correct 124 ms 27272 KB Output is correct
6 Correct 189 ms 27256 KB Output is correct
7 Correct 105 ms 26892 KB Output is correct
8 Correct 1505 ms 47964 KB Output is correct
9 Correct 1566 ms 48048 KB Output is correct
10 Correct 105 ms 26736 KB Output is correct
11 Correct 1417 ms 56492 KB Output is correct
12 Correct 1304 ms 56488 KB Output is correct
13 Correct 850 ms 56492 KB Output is correct
14 Correct 106 ms 26804 KB Output is correct
15 Correct 979 ms 48436 KB Output is correct
16 Correct 1465 ms 48640 KB Output is correct
17 Correct 1753 ms 49544 KB Output is correct
18 Correct 1433 ms 49116 KB Output is correct
19 Correct 1160 ms 53412 KB Output is correct
20 Correct 1833 ms 52800 KB Output is correct
21 Correct 1408 ms 48164 KB Output is correct
22 Correct 1388 ms 48152 KB Output is correct
23 Correct 1630 ms 48536 KB Output is correct
24 Correct 1400 ms 48428 KB Output is correct
25 Correct 1295 ms 50260 KB Output is correct
26 Correct 1360 ms 49016 KB Output is correct
27 Correct 1629 ms 47980 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 108 ms 26808 KB Output is correct
2 Correct 144 ms 27860 KB Output is correct
3 Correct 142 ms 27984 KB Output is correct
4 Correct 139 ms 27996 KB Output is correct
5 Correct 124 ms 27272 KB Output is correct
6 Correct 189 ms 27256 KB Output is correct
7 Correct 105 ms 26892 KB Output is correct
8 Correct 1505 ms 47964 KB Output is correct
9 Correct 1566 ms 48048 KB Output is correct
10 Correct 105 ms 26736 KB Output is correct
11 Correct 1417 ms 56492 KB Output is correct
12 Correct 1304 ms 56488 KB Output is correct
13 Correct 850 ms 56492 KB Output is correct
14 Correct 106 ms 26804 KB Output is correct
15 Correct 979 ms 48436 KB Output is correct
16 Correct 1465 ms 48640 KB Output is correct
17 Correct 1753 ms 49544 KB Output is correct
18 Correct 1433 ms 49116 KB Output is correct
19 Correct 1160 ms 53412 KB Output is correct
20 Correct 1833 ms 52800 KB Output is correct
21 Correct 1408 ms 48164 KB Output is correct
22 Correct 1388 ms 48152 KB Output is correct
23 Correct 1630 ms 48536 KB Output is correct
24 Correct 1400 ms 48428 KB Output is correct
25 Correct 1295 ms 50260 KB Output is correct
26 Correct 1360 ms 49016 KB Output is correct
27 Correct 1629 ms 47980 KB Output is correct
28 Correct 109 ms 26764 KB Output is correct
29 Correct 242 ms 28596 KB Output is correct
30 Correct 178 ms 28520 KB Output is correct
31 Correct 241 ms 28768 KB Output is correct
32 Correct 178 ms 27892 KB Output is correct
33 Correct 221 ms 27948 KB Output is correct
34 Correct 107 ms 26740 KB Output is correct
35 Correct 2631 ms 48232 KB Output is correct
36 Correct 2217 ms 48864 KB Output is correct
37 Execution timed out 3569 ms 48092 KB Time limit exceeded
38 Halted 0 ms 0 KB -