oj.uz

답안 #409069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409069 2021-05-20T06:55:50 Z balbit Inside information (BOI21_servers) C++14
52.5 / 100
 3500 ms 58768 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 = 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) {
            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 126 ms 26804 KB Output is correct
2 Correct 172 ms 27892 KB Output is correct
3 Correct 170 ms 28096 KB Output is correct
4 Correct 164 ms 28056 KB Output is correct
5 Correct 152 ms 27364 KB Output is correct
6 Correct 174 ms 27352 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 26804 KB Output is correct
2 Correct 172 ms 27892 KB Output is correct
3 Correct 170 ms 28096 KB Output is correct
4 Correct 164 ms 28056 KB Output is correct
5 Correct 152 ms 27364 KB Output is correct
6 Correct 174 ms 27352 KB Output is correct
7 Correct 133 ms 26784 KB Output is correct
8 Correct 250 ms 28560 KB Output is correct
9 Correct 198 ms 28536 KB Output is correct
10 Correct 242 ms 28640 KB Output is correct
11 Correct 203 ms 27860 KB Output is correct
12 Correct 229 ms 27872 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 26808 KB Output is correct
2 Correct 1762 ms 48048 KB Output is correct
3 Correct 1764 ms 48104 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 26808 KB Output is correct
2 Correct 1762 ms 48048 KB Output is correct
3 Correct 1764 ms 48104 KB Output is correct
4 Correct 129 ms 26788 KB Output is correct
5 Correct 2832 ms 48228 KB Output is correct
6 Correct 2538 ms 49556 KB Output is correct
7 Execution timed out 3545 ms 48896 KB Time limit exceeded

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 26764 KB Output is correct
2 Correct 1532 ms 56528 KB Output is correct
3 Correct 1517 ms 56492 KB Output is correct
4 Correct 1157 ms 56496 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 26764 KB Output is correct
2 Correct 1532 ms 56528 KB Output is correct
3 Correct 1517 ms 56492 KB Output is correct
4 Correct 1157 ms 56496 KB Output is correct
5 Correct 126 ms 26704 KB Output is correct
6 Execution timed out 3578 ms 58720 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 26808 KB Output is correct
2 Correct 1283 ms 48372 KB Output is correct
3 Correct 1927 ms 48516 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 26808 KB Output is correct
2 Correct 1283 ms 48372 KB Output is correct
3 Correct 1927 ms 48516 KB Output is correct
4 Correct 140 ms 26740 KB Output is correct
5 Execution timed out 3586 ms 49936 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 26804 KB Output is correct
2 Correct 1562 ms 56492 KB Output is correct
3 Correct 1617 ms 56492 KB Output is correct
4 Correct 1153 ms 56488 KB Output is correct
5 Correct 125 ms 26804 KB Output is correct
6 Correct 1319 ms 48248 KB Output is correct
7 Correct 1907 ms 48516 KB Output is correct
8 Correct 2163 ms 49324 KB Output is correct
9 Correct 1892 ms 49072 KB Output is correct
10 Correct 1703 ms 53368 KB Output is correct
11 Correct 2016 ms 52724 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 26804 KB Output is correct
2 Correct 1562 ms 56492 KB Output is correct
3 Correct 1617 ms 56492 KB Output is correct
4 Correct 1153 ms 56488 KB Output is correct
5 Correct 125 ms 26804 KB Output is correct
6 Correct 1319 ms 48248 KB Output is correct
7 Correct 1907 ms 48516 KB Output is correct
8 Correct 2163 ms 49324 KB Output is correct
9 Correct 1892 ms 49072 KB Output is correct
10 Correct 1703 ms 53368 KB Output is correct
11 Correct 2016 ms 52724 KB Output is correct
12 Correct 135 ms 26688 KB Output is correct
13 Execution timed out 3567 ms 58768 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 26816 KB Output is correct
2 Correct 170 ms 27864 KB Output is correct
3 Correct 177 ms 28088 KB Output is correct
4 Correct 175 ms 27956 KB Output is correct
5 Correct 158 ms 27360 KB Output is correct
6 Correct 175 ms 27236 KB Output is correct
7 Correct 130 ms 26932 KB Output is correct
8 Correct 2183 ms 48180 KB Output is correct
9 Correct 2328 ms 48060 KB Output is correct
10 Correct 128 ms 26808 KB Output is correct
11 Correct 1943 ms 56488 KB Output is correct
12 Correct 1615 ms 56496 KB Output is correct
13 Correct 1257 ms 56488 KB Output is correct
14 Correct 134 ms 26752 KB Output is correct
15 Correct 1403 ms 48200 KB Output is correct
16 Correct 2878 ms 48508 KB Output is correct
17 Correct 2638 ms 49336 KB Output is correct
18 Correct 2160 ms 48964 KB Output is correct
19 Correct 1862 ms 53360 KB Output is correct
20 Correct 2170 ms 52864 KB Output is correct
21 Correct 2138 ms 48052 KB Output is correct
22 Correct 2001 ms 48168 KB Output is correct
23 Correct 2323 ms 48532 KB Output is correct
24 Correct 2162 ms 48536 KB Output is correct
25 Correct 2382 ms 50252 KB Output is correct
26 Correct 1902 ms 48888 KB Output is correct
27 Correct 1960 ms 47940 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 26816 KB Output is correct
2 Correct 170 ms 27864 KB Output is correct
3 Correct 177 ms 28088 KB Output is correct
4 Correct 175 ms 27956 KB Output is correct
5 Correct 158 ms 27360 KB Output is correct
6 Correct 175 ms 27236 KB Output is correct
7 Correct 130 ms 26932 KB Output is correct
8 Correct 2183 ms 48180 KB Output is correct
9 Correct 2328 ms 48060 KB Output is correct
10 Correct 128 ms 26808 KB Output is correct
11 Correct 1943 ms 56488 KB Output is correct
12 Correct 1615 ms 56496 KB Output is correct
13 Correct 1257 ms 56488 KB Output is correct
14 Correct 134 ms 26752 KB Output is correct
15 Correct 1403 ms 48200 KB Output is correct
16 Correct 2878 ms 48508 KB Output is correct
17 Correct 2638 ms 49336 KB Output is correct
18 Correct 2160 ms 48964 KB Output is correct
19 Correct 1862 ms 53360 KB Output is correct
20 Correct 2170 ms 52864 KB Output is correct
21 Correct 2138 ms 48052 KB Output is correct
22 Correct 2001 ms 48168 KB Output is correct
23 Correct 2323 ms 48532 KB Output is correct
24 Correct 2162 ms 48536 KB Output is correct
25 Correct 2382 ms 50252 KB Output is correct
26 Correct 1902 ms 48888 KB Output is correct
27 Correct 1960 ms 47940 KB Output is correct
28 Correct 129 ms 26700 KB Output is correct
29 Correct 250 ms 28684 KB Output is correct
30 Correct 206 ms 29432 KB Output is correct
31 Correct 252 ms 29548 KB Output is correct
32 Correct 210 ms 28732 KB Output is correct
33 Correct 234 ms 28744 KB Output is correct
34 Correct 164 ms 27580 KB Output is correct
35 Correct 3433 ms 49128 KB Output is correct
36 Correct 2899 ms 49672 KB Output is correct
37 Execution timed out 3537 ms 49116 KB Time limit exceeded
38 Halted 0 ms 0 KB -