oj.uz

답안 #409061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409061 2021-05-20T06:43:16 Z balbit Inside information (BOI21_servers) C++14
50 / 100
 401 ms 56508 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;
    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;
    }

    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 = 200;
    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) {
        ans[p.s] = 1;
        int v = p.f; int ansi = p.s;
        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:147:9: warning: unused variable 'hoho' [-Wunused-variable]
  147 |     int hoho = HH.t;
      |         ^~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26812 KB Output is correct
2 Correct 81 ms 27920 KB Output is correct
3 Correct 80 ms 28080 KB Output is correct
4 Correct 99 ms 27980 KB Output is correct
5 Correct 65 ms 27268 KB Output is correct
6 Correct 88 ms 27236 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26812 KB Output is correct
2 Correct 81 ms 27920 KB Output is correct
3 Correct 80 ms 28080 KB Output is correct
4 Correct 99 ms 27980 KB Output is correct
5 Correct 65 ms 27268 KB Output is correct
6 Correct 88 ms 27236 KB Output is correct
7 Incorrect 61 ms 26680 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 26840 KB Output is correct
2 Correct 356 ms 48176 KB Output is correct
3 Correct 391 ms 48052 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 26840 KB Output is correct
2 Correct 356 ms 48176 KB Output is correct
3 Correct 391 ms 48052 KB Output is correct
4 Incorrect 63 ms 26736 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 26724 KB Output is correct
2 Correct 145 ms 56444 KB Output is correct
3 Correct 164 ms 56500 KB Output is correct
4 Correct 145 ms 56508 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 26724 KB Output is correct
2 Correct 145 ms 56444 KB Output is correct
3 Correct 164 ms 56500 KB Output is correct
4 Correct 145 ms 56508 KB Output is correct
5 Incorrect 67 ms 26792 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26788 KB Output is correct
2 Correct 266 ms 48264 KB Output is correct
3 Correct 183 ms 48596 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 26788 KB Output is correct
2 Correct 266 ms 48264 KB Output is correct
3 Correct 183 ms 48596 KB Output is correct
4 Incorrect 65 ms 26772 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 26740 KB Output is correct
2 Correct 146 ms 56440 KB Output is correct
3 Correct 152 ms 56424 KB Output is correct
4 Correct 141 ms 56484 KB Output is correct
5 Correct 63 ms 26820 KB Output is correct
6 Correct 229 ms 48308 KB Output is correct
7 Correct 197 ms 48480 KB Output is correct
8 Correct 300 ms 49388 KB Output is correct
9 Correct 256 ms 49044 KB Output is correct
10 Correct 193 ms 53424 KB Output is correct
11 Correct 335 ms 52780 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 26740 KB Output is correct
2 Correct 146 ms 56440 KB Output is correct
3 Correct 152 ms 56424 KB Output is correct
4 Correct 141 ms 56484 KB Output is correct
5 Correct 63 ms 26820 KB Output is correct
6 Correct 229 ms 48308 KB Output is correct
7 Correct 197 ms 48480 KB Output is correct
8 Correct 300 ms 49388 KB Output is correct
9 Correct 256 ms 49044 KB Output is correct
10 Correct 193 ms 53424 KB Output is correct
11 Correct 335 ms 52780 KB Output is correct
12 Incorrect 59 ms 26688 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 26708 KB Output is correct
2 Correct 82 ms 27856 KB Output is correct
3 Correct 96 ms 28072 KB Output is correct
4 Correct 81 ms 27980 KB Output is correct
5 Correct 65 ms 27340 KB Output is correct
6 Correct 86 ms 27236 KB Output is correct
7 Correct 60 ms 26800 KB Output is correct
8 Correct 357 ms 48052 KB Output is correct
9 Correct 401 ms 48052 KB Output is correct
10 Correct 52 ms 26704 KB Output is correct
11 Correct 141 ms 56504 KB Output is correct
12 Correct 149 ms 56432 KB Output is correct
13 Correct 148 ms 56484 KB Output is correct
14 Correct 57 ms 26808 KB Output is correct
15 Correct 235 ms 48208 KB Output is correct
16 Correct 210 ms 48496 KB Output is correct
17 Correct 312 ms 49252 KB Output is correct
18 Correct 242 ms 48956 KB Output is correct
19 Correct 227 ms 53368 KB Output is correct
20 Correct 300 ms 52744 KB Output is correct
21 Correct 365 ms 47984 KB Output is correct
22 Correct 380 ms 48168 KB Output is correct
23 Correct 346 ms 48532 KB Output is correct
24 Correct 324 ms 48536 KB Output is correct
25 Correct 254 ms 50364 KB Output is correct
26 Correct 158 ms 48972 KB Output is correct
27 Correct 144 ms 47976 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 26708 KB Output is correct
2 Correct 82 ms 27856 KB Output is correct
3 Correct 96 ms 28072 KB Output is correct
4 Correct 81 ms 27980 KB Output is correct
5 Correct 65 ms 27340 KB Output is correct
6 Correct 86 ms 27236 KB Output is correct
7 Correct 60 ms 26800 KB Output is correct
8 Correct 357 ms 48052 KB Output is correct
9 Correct 401 ms 48052 KB Output is correct
10 Correct 52 ms 26704 KB Output is correct
11 Correct 141 ms 56504 KB Output is correct
12 Correct 149 ms 56432 KB Output is correct
13 Correct 148 ms 56484 KB Output is correct
14 Correct 57 ms 26808 KB Output is correct
15 Correct 235 ms 48208 KB Output is correct
16 Correct 210 ms 48496 KB Output is correct
17 Correct 312 ms 49252 KB Output is correct
18 Correct 242 ms 48956 KB Output is correct
19 Correct 227 ms 53368 KB Output is correct
20 Correct 300 ms 52744 KB Output is correct
21 Correct 365 ms 47984 KB Output is correct
22 Correct 380 ms 48168 KB Output is correct
23 Correct 346 ms 48532 KB Output is correct
24 Correct 324 ms 48536 KB Output is correct
25 Correct 254 ms 50364 KB Output is correct
26 Correct 158 ms 48972 KB Output is correct
27 Correct 144 ms 47976 KB Output is correct
28 Incorrect 61 ms 26688 KB Extra information in the output file
29 Halted 0 ms 0 KB -