oj.uz

답안 #409070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409070 2021-05-20T06:56:41 Z balbit Inside information (BOI21_servers) C++14
52.5 / 100
 3500 ms 58804 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 = 150;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 26808 KB Output is correct
2 Correct 201 ms 27852 KB Output is correct
3 Correct 200 ms 28084 KB Output is correct
4 Correct 193 ms 28000 KB Output is correct
5 Correct 180 ms 27328 KB Output is correct
6 Correct 205 ms 27236 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 26808 KB Output is correct
2 Correct 201 ms 27852 KB Output is correct
3 Correct 200 ms 28084 KB Output is correct
4 Correct 193 ms 28000 KB Output is correct
5 Correct 180 ms 27328 KB Output is correct
6 Correct 205 ms 27236 KB Output is correct
7 Correct 154 ms 26732 KB Output is correct
8 Correct 273 ms 28584 KB Output is correct
9 Correct 267 ms 28584 KB Output is correct
10 Correct 264 ms 28588 KB Output is correct
11 Correct 246 ms 27888 KB Output is correct
12 Correct 259 ms 27804 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 26820 KB Output is correct
2 Correct 2779 ms 48052 KB Output is correct
3 Correct 2638 ms 48064 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 26820 KB Output is correct
2 Correct 2779 ms 48052 KB Output is correct
3 Correct 2638 ms 48064 KB Output is correct
4 Correct 155 ms 26748 KB Output is correct
5 Execution timed out 3565 ms 47776 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 26788 KB Output is correct
2 Correct 2304 ms 56488 KB Output is correct
3 Correct 2317 ms 56488 KB Output is correct
4 Correct 1660 ms 56612 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 26788 KB Output is correct
2 Correct 2304 ms 56488 KB Output is correct
3 Correct 2317 ms 56488 KB Output is correct
4 Correct 1660 ms 56612 KB Output is correct
5 Correct 147 ms 26676 KB Output is correct
6 Execution timed out 3579 ms 58804 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 26820 KB Output is correct
2 Correct 1779 ms 48312 KB Output is correct
3 Correct 2947 ms 48524 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 26820 KB Output is correct
2 Correct 1779 ms 48312 KB Output is correct
3 Correct 2947 ms 48524 KB Output is correct
4 Correct 156 ms 26704 KB Output is correct
5 Execution timed out 3552 ms 49972 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 26780 KB Output is correct
2 Correct 2419 ms 56488 KB Output is correct
3 Correct 2361 ms 56612 KB Output is correct
4 Correct 1673 ms 56500 KB Output is correct
5 Correct 152 ms 26808 KB Output is correct
6 Correct 1759 ms 48268 KB Output is correct
7 Correct 2793 ms 48512 KB Output is correct
8 Correct 3211 ms 49248 KB Output is correct
9 Correct 2990 ms 48952 KB Output is correct
10 Correct 2348 ms 53360 KB Output is correct
11 Correct 2628 ms 52868 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 26780 KB Output is correct
2 Correct 2419 ms 56488 KB Output is correct
3 Correct 2361 ms 56612 KB Output is correct
4 Correct 1673 ms 56500 KB Output is correct
5 Correct 152 ms 26808 KB Output is correct
6 Correct 1759 ms 48268 KB Output is correct
7 Correct 2793 ms 48512 KB Output is correct
8 Correct 3211 ms 49248 KB Output is correct
9 Correct 2990 ms 48952 KB Output is correct
10 Correct 2348 ms 53360 KB Output is correct
11 Correct 2628 ms 52868 KB Output is correct
12 Correct 148 ms 26752 KB Output is correct
13 Execution timed out 3552 ms 58760 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 26804 KB Output is correct
2 Correct 221 ms 27892 KB Output is correct
3 Correct 196 ms 28080 KB Output is correct
4 Correct 281 ms 27984 KB Output is correct
5 Correct 185 ms 27364 KB Output is correct
6 Correct 203 ms 27296 KB Output is correct
7 Correct 160 ms 26804 KB Output is correct
8 Correct 2480 ms 48048 KB Output is correct
9 Correct 2526 ms 48052 KB Output is correct
10 Correct 146 ms 26812 KB Output is correct
11 Correct 2119 ms 56500 KB Output is correct
12 Correct 2401 ms 56488 KB Output is correct
13 Correct 1567 ms 56488 KB Output is correct
14 Correct 153 ms 26780 KB Output is correct
15 Correct 1796 ms 48320 KB Output is correct
16 Correct 2745 ms 48524 KB Output is correct
17 Correct 3064 ms 49324 KB Output is correct
18 Correct 2815 ms 48948 KB Output is correct
19 Correct 2340 ms 53364 KB Output is correct
20 Correct 2905 ms 52716 KB Output is correct
21 Correct 2549 ms 48056 KB Output is correct
22 Correct 2556 ms 48144 KB Output is correct
23 Correct 2537 ms 48536 KB Output is correct
24 Correct 2586 ms 48536 KB Output is correct
25 Correct 2605 ms 50232 KB Output is correct
26 Correct 2542 ms 48916 KB Output is correct
27 Correct 2683 ms 47944 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 26804 KB Output is correct
2 Correct 221 ms 27892 KB Output is correct
3 Correct 196 ms 28080 KB Output is correct
4 Correct 281 ms 27984 KB Output is correct
5 Correct 185 ms 27364 KB Output is correct
6 Correct 203 ms 27296 KB Output is correct
7 Correct 160 ms 26804 KB Output is correct
8 Correct 2480 ms 48048 KB Output is correct
9 Correct 2526 ms 48052 KB Output is correct
10 Correct 146 ms 26812 KB Output is correct
11 Correct 2119 ms 56500 KB Output is correct
12 Correct 2401 ms 56488 KB Output is correct
13 Correct 1567 ms 56488 KB Output is correct
14 Correct 153 ms 26780 KB Output is correct
15 Correct 1796 ms 48320 KB Output is correct
16 Correct 2745 ms 48524 KB Output is correct
17 Correct 3064 ms 49324 KB Output is correct
18 Correct 2815 ms 48948 KB Output is correct
19 Correct 2340 ms 53364 KB Output is correct
20 Correct 2905 ms 52716 KB Output is correct
21 Correct 2549 ms 48056 KB Output is correct
22 Correct 2556 ms 48144 KB Output is correct
23 Correct 2537 ms 48536 KB Output is correct
24 Correct 2586 ms 48536 KB Output is correct
25 Correct 2605 ms 50232 KB Output is correct
26 Correct 2542 ms 48916 KB Output is correct
27 Correct 2683 ms 47944 KB Output is correct
28 Correct 152 ms 26668 KB Output is correct
29 Correct 295 ms 28560 KB Output is correct
30 Correct 251 ms 28500 KB Output is correct
31 Correct 285 ms 28760 KB Output is correct
32 Correct 247 ms 27848 KB Output is correct
33 Correct 253 ms 27844 KB Output is correct
34 Correct 159 ms 26772 KB Output is correct
35 Execution timed out 3560 ms 47772 KB Time limit exceeded
36 Halted 0 ms 0 KB -