oj.uz

답안 #409067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409067 2021-05-20T06:52:35 Z balbit Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 58732 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 = 200000;
    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) {
//        for (int tt : hey2[i]) ans[tt] += 1 + now[i];
//    }
//    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;
      |         ^~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26724 KB Output is correct
2 Correct 90 ms 27860 KB Output is correct
3 Correct 101 ms 28024 KB Output is correct
4 Correct 91 ms 28056 KB Output is correct
5 Correct 65 ms 27252 KB Output is correct
6 Correct 86 ms 27292 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26724 KB Output is correct
2 Correct 90 ms 27860 KB Output is correct
3 Correct 101 ms 28024 KB Output is correct
4 Correct 91 ms 28056 KB Output is correct
5 Correct 65 ms 27252 KB Output is correct
6 Correct 86 ms 27292 KB Output is correct
7 Correct 882 ms 26816 KB Output is correct
8 Execution timed out 3598 ms 28176 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 26832 KB Output is correct
2 Correct 350 ms 48032 KB Output is correct
3 Correct 371 ms 48044 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 26832 KB Output is correct
2 Correct 350 ms 48032 KB Output is correct
3 Correct 371 ms 48044 KB Output is correct
4 Correct 864 ms 26716 KB Output is correct
5 Execution timed out 3599 ms 47776 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 26724 KB Output is correct
2 Correct 150 ms 56428 KB Output is correct
3 Correct 144 ms 56508 KB Output is correct
4 Correct 165 ms 56488 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 26724 KB Output is correct
2 Correct 150 ms 56428 KB Output is correct
3 Correct 144 ms 56508 KB Output is correct
4 Correct 165 ms 56488 KB Output is correct
5 Correct 857 ms 26684 KB Output is correct
6 Execution timed out 3601 ms 58724 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26764 KB Output is correct
2 Correct 233 ms 48316 KB Output is correct
3 Correct 203 ms 48520 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26764 KB Output is correct
2 Correct 233 ms 48316 KB Output is correct
3 Correct 203 ms 48520 KB Output is correct
4 Correct 909 ms 26704 KB Output is correct
5 Execution timed out 3565 ms 49780 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 26804 KB Output is correct
2 Correct 168 ms 56636 KB Output is correct
3 Correct 152 ms 56496 KB Output is correct
4 Correct 150 ms 56488 KB Output is correct
5 Correct 66 ms 26812 KB Output is correct
6 Correct 239 ms 48268 KB Output is correct
7 Correct 182 ms 48492 KB Output is correct
8 Correct 295 ms 49288 KB Output is correct
9 Correct 268 ms 48988 KB Output is correct
10 Correct 190 ms 53308 KB Output is correct
11 Correct 298 ms 52740 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 26804 KB Output is correct
2 Correct 168 ms 56636 KB Output is correct
3 Correct 152 ms 56496 KB Output is correct
4 Correct 150 ms 56488 KB Output is correct
5 Correct 66 ms 26812 KB Output is correct
6 Correct 239 ms 48268 KB Output is correct
7 Correct 182 ms 48492 KB Output is correct
8 Correct 295 ms 49288 KB Output is correct
9 Correct 268 ms 48988 KB Output is correct
10 Correct 190 ms 53308 KB Output is correct
11 Correct 298 ms 52740 KB Output is correct
12 Correct 850 ms 26692 KB Output is correct
13 Execution timed out 3574 ms 58732 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 26748 KB Output is correct
2 Correct 99 ms 27860 KB Output is correct
3 Correct 82 ms 28112 KB Output is correct
4 Correct 80 ms 28052 KB Output is correct
5 Correct 64 ms 27380 KB Output is correct
6 Correct 100 ms 27236 KB Output is correct
7 Correct 59 ms 26804 KB Output is correct
8 Correct 364 ms 48008 KB Output is correct
9 Correct 400 ms 48052 KB Output is correct
10 Correct 53 ms 26716 KB Output is correct
11 Correct 142 ms 56488 KB Output is correct
12 Correct 145 ms 56504 KB Output is correct
13 Correct 142 ms 56488 KB Output is correct
14 Correct 61 ms 26772 KB Output is correct
15 Correct 224 ms 48280 KB Output is correct
16 Correct 184 ms 48560 KB Output is correct
17 Correct 311 ms 49268 KB Output is correct
18 Correct 237 ms 48936 KB Output is correct
19 Correct 202 ms 53340 KB Output is correct
20 Correct 352 ms 52804 KB Output is correct
21 Correct 324 ms 48032 KB Output is correct
22 Correct 370 ms 48148 KB Output is correct
23 Correct 346 ms 48532 KB Output is correct
24 Correct 355 ms 48456 KB Output is correct
25 Correct 248 ms 50244 KB Output is correct
26 Correct 166 ms 48964 KB Output is correct
27 Correct 149 ms 48008 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 26748 KB Output is correct
2 Correct 99 ms 27860 KB Output is correct
3 Correct 82 ms 28112 KB Output is correct
4 Correct 80 ms 28052 KB Output is correct
5 Correct 64 ms 27380 KB Output is correct
6 Correct 100 ms 27236 KB Output is correct
7 Correct 59 ms 26804 KB Output is correct
8 Correct 364 ms 48008 KB Output is correct
9 Correct 400 ms 48052 KB Output is correct
10 Correct 53 ms 26716 KB Output is correct
11 Correct 142 ms 56488 KB Output is correct
12 Correct 145 ms 56504 KB Output is correct
13 Correct 142 ms 56488 KB Output is correct
14 Correct 61 ms 26772 KB Output is correct
15 Correct 224 ms 48280 KB Output is correct
16 Correct 184 ms 48560 KB Output is correct
17 Correct 311 ms 49268 KB Output is correct
18 Correct 237 ms 48936 KB Output is correct
19 Correct 202 ms 53340 KB Output is correct
20 Correct 352 ms 52804 KB Output is correct
21 Correct 324 ms 48032 KB Output is correct
22 Correct 370 ms 48148 KB Output is correct
23 Correct 346 ms 48532 KB Output is correct
24 Correct 355 ms 48456 KB Output is correct
25 Correct 248 ms 50244 KB Output is correct
26 Correct 166 ms 48964 KB Output is correct
27 Correct 149 ms 48008 KB Output is correct
28 Correct 907 ms 26728 KB Output is correct
29 Execution timed out 3572 ms 28276 KB Time limit exceeded
30 Halted 0 ms 0 KB -