oj.uz

Submission #402999

# Submission time Handle Problem Language Result Execution time Memory
402999 2021-05-12T16:08:34 Z b00n0rp Inside information (BOI21_servers) C++17
100 / 100
 410 ms 71152 KB 
// --------------------------------------------------<TEMPLATE>--------------------------------------------------
// --------------------<optimizations>--------------------
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
*/ 
// -------------------</optimizations>--------------------
 
// ---------------<Headers and namespaces>----------------
#include <bits/stdc++.h>
using namespace std;
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
 
// ---------------</Headers and namespaces>---------------
 
// -----------------<Defines and typedefs>----------------
// typedef tree<int,null_type,less<int>,rb_tree_tag, 
// tree_order_statistics_node_update> indexed_set; // use less_equal for multiset
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the iterator to kth largest element.(0-based)
 
typedef long double LD;
typedef long long ll;
#define int ll
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
 
/*
// -----<SCANF>-----
#define sfi(x) scanf("%d",&x);
#define sfi2(x,y) scanf("%d%d",&x,&y);
#define sfi3(x,y,z) scanf("%d%d%d",&x,&y,&z);
 
#define sfl(x) scanf("%lld",&x);
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
#define sfl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z);
#define sfl4(x,y,z,x1) scanf("%lld%lld%lld%lld",&x,&y,&z,&x1);
#define sfl5(x,y,z,x1,y1) scanf("%lld%lld%lld%lld%lld",&x,&y,&z,&x1,&y1);
#define sfl6(x,y,z,x1,y1,z1) scanf("%lld%lld%lld%lld%lld%lld",&x,&y,&z,&x1,&y1,&z1);
 
#define sfs(x) scanf("%s",x);
#define sfs2(x,y) scanf("%s%s",x,y);
#define sfs3(x,y,z) scanf("%s%s%s",x,y,z);
// ----</SCANF>-----
 
// ----<PRINTF>-----
#define pfi(x) printf("%d\n",x);
#define pfi2(x,y) printf("%d %d\n",x,y);
#define pfi3(x,y,z) printf("%d %d %d\n",x,y,z);
 
#define pfl(x) printf("%lld\n",x);
#define pfl2(x,y) printf("%lld %lld\n",x,y);
#define pfl3(x,y,z) printf("%lld %lld %lld\n",x,y,z);
 
#define pfs(x) printf("%s\n",x);
#define pfs2(x,y) printf("%s %s\n",x,y);
#define pfs3(x,y,z) printf("%s %s %s\n",x,y,z);
 
#define pwe(x) printf("%lld ",x); // print without end
// ----</PRINTF>----
*/
#define FLSH fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x) cout << fixed << setprecision(x); 
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
// ----------------</Defines and typedefs>----------------
 
// -------------------<Debugging stuff>-------------------
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
// ------------------</Debugging stuff>-------------------
 
// ------------------------<Consts>-----------------------
const int MAXN = 120005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);
 
#ifdef int
const int INF=1e16;
#else
const int INF=1e9;
#endif
 
const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;
// -----------------------</Consts>-----------------------
/*
// -------------------------<RNG>-------------------------
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.
 
// ------------------------</RNG>-------------------------
 
// ----------------------<MATH>---------------------------
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
int add(int a, int b, int c = MOD){int res=a+b;return(res>=c?res-c:res);}
int mod_neg(int a, int b, int c = MOD){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
int mul(int a, int b, int c = MOD){ll res=(ll)a*b;return(res>=c?res%c:res);}
int muln(int a, int b, int c = MOD){ll res=(ll)a*b;return ((res%c)+c)%c;}
ll mulmod(ll a,ll b, ll m = MOD){ll q = (ll)(((LD)a*(LD)b)/(LD)m);ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
template<typename T>T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
template<typename T>T power(T e, T n, T m = MOD){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T>T mod_inverse(T a, T n = MOD){T x,y,z=0;T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
 
const int FACSZ = 1; // Make sure to change this
 
int fact[FACSZ],ifact[FACSZ];
 
void precom(int c = MOD){
    fact[0] = 1;
    FOR(i,1,FACSZ) fact[i] = mul(fact[i-1],i,c);
    ifact[FACSZ-1] = mod_inverse(fact[FACSZ-1],c);
    REPD(i,FACSZ-1){
        ifact[i] = mul(i+1,ifact[i+1],c);
    }
}
 
int ncr(int n,int r,int c = MOD){
    return mul(mul(ifact[r],ifact[n-r],c),fact[n],c);
} 
*/
// ----------------------</MATH>--------------------------
// --------------------------------------------------</TEMPLATE>--------------------------------------------------
 
void solvethetestcase();
 
signed main(){
    // comment when using scanf,printf
    FAST_IO
    int t = 1;
    // (UNCOMMENT FOR MULTIPLE TEST CASES)
    // cin >> t;
    FOR(testcase,1,t+1){
        // (UNCOMMENT FOR CODEJAM)
        // printf("Case #%lld: ",testcase); 
        solvethetestcase();
    }
}   
 
int n,q;
vector<pair<int,pii> > queries;
vpii adj[MAXN];
int dep[MAXN],edge_val[MAXN],par[MAXN][21];
int up_inc[MAXN],up_dec[MAXN];
vi gg[MAXN],gg_inc[MAXN],gg_dec[MAXN];
int seg[4*MAXN],ans[2*MAXN];

void dfs(int u,int p,int d){
    par[u][0] = p;
    dep[u] = d;
    for(auto v:adj[u]){
        if(v.F == p) continue;
        edge_val[v.F] = v.S;
        if(v.S < edge_val[u]){
            up_inc[v.F] = up_inc[u];
            up_dec[v.F] = u;
        }
        else{
            up_dec[v.F] = up_dec[u];
            up_inc[v.F] = u;
        }
        dfs(v.F,u,d+1);
    }
}

int incpath(int u,int v){
    int d = max(dep[up_inc[u]],dep[up_dec[v]]);
    int vp = edge_val[v];
    if(dep[u] < dep[v]){
        FORD(j,20,0){
            if(dep[v]-(1<<j) > dep[u]) v = par[v][j];
        }
        if(par[v][0] == u){
            if(d > dep[u]) return INF;
            return vp;
        }
        v = par[v][0];
    }
    else if(dep[v] < dep[u]){
        FORD(j,20,0){
            if(dep[u]-(1<<j) > dep[v]) u = par[u][j];
        }
        if(par[u][0] == v){
            if(d > dep[v]) return INF;
            return edge_val[u];
        }
        u = par[u][0];
    }
    FORD(j,20,0){
        if(par[u][j] != par[v][j]){
            u = par[u][j];
            v = par[v][j];
        }
    }
    if(d <= dep[u]-1 and edge_val[u] < edge_val[v]) return vp;  
    return INF;
}

void update(int t,int val){
    t += 2*MAXN;
    while(t){
        seg[t] += val;
        t /= 2;
    }
}

int query(int t){
    int l = 0,r = t+1;
    l += 2*MAXN;
    r += 2*MAXN;
    int res = 0;
    while(l < r){
        if(l&1) res += seg[l++];
        if(r&1) res += seg[--r];
        l >>= 1;
        r >>= 1;
    }
    return res;
}

void dfs_solve(int u){
    if(u != 1) update(edge_val[u],1);
    for(auto t:gg_inc[u]) ans[t] -= query(t);
    for(auto v:adj[u]){
        if(par[v.F][0] == u) dfs_solve(v.F);
    }
    for(auto t:gg[u]) ans[t] += query(t);
    for(auto t:gg_dec[u]) update(t,-1);
}
 
void solvethetestcase(){
    cin >> n >> q;
    REP(i,q+n-1){
        char type; cin >> type;
        if(type == 'S'){
            int u,v; cin >> u >> v;
            adj[u].pb({v,i});
            adj[v].pb({u,i});
            queries.pb({1,{u,v}});
        }
        else if(type == 'Q'){
            int u,v; cin >> u >> v;
            queries.pb({2,{v,u}});
            // tell whether there is an increasing path from v->u 
            // st. value of last edge <= i
        }
        else{
            int u; cin >> u;
            queries.pb({3,{u,0}});
            // number of increasing paths starting from u
            // st. value of last edge <= i
        }
    }
    FOR(i,1,n+1){
        reverse(all(adj[i]));
    }
    dfs(1,1,0);
    FOR(j,1,20){
        FOR(i,1,n+1){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    REP(i,q+n-1){
        if(queries[i].F == 1){
            int u = queries[i].S.F;
            int v = queries[i].S.S;
            if(par[u][0] == v) swap(u,v);
            gg_dec[up_dec[v]].pb(i);
        }
        else if(queries[i].F == 3){
            int u = queries[i].S.F;
            gg[u].pb(i);
            gg_inc[up_inc[u]].pb(i);
        }
    }
    dfs_solve(1);
    REP(i,q+n-1){
        if(queries[i].F == 2){
            int u = queries[i].S.F;
            int v = queries[i].S.S;
            if(u == v or incpath(u,v) < i) cout << "yes\n";
            else cout << "no\n";
        }
        else if(queries[i].F == 3){
            cout << ans[i]+1 << "\n";
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 15660 KB Output is correct
2 Correct 70 ms 19264 KB Output is correct
3 Correct 64 ms 19376 KB Output is correct
4 Correct 75 ms 19404 KB Output is correct
5 Correct 62 ms 17712 KB Output is correct
6 Correct 58 ms 17992 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 15660 KB Output is correct
2 Correct 70 ms 19264 KB Output is correct
3 Correct 64 ms 19376 KB Output is correct
4 Correct 75 ms 19404 KB Output is correct
5 Correct 62 ms 17712 KB Output is correct
6 Correct 58 ms 17992 KB Output is correct
7 Correct 50 ms 16096 KB Output is correct
8 Correct 81 ms 21536 KB Output is correct
9 Correct 72 ms 21356 KB Output is correct
10 Correct 80 ms 21552 KB Output is correct
11 Correct 73 ms 20024 KB Output is correct
12 Correct 64 ms 20108 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15664 KB Output is correct
2 Correct 213 ms 54840 KB Output is correct
3 Correct 206 ms 54764 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15664 KB Output is correct
2 Correct 213 ms 54840 KB Output is correct
3 Correct 206 ms 54764 KB Output is correct
4 Correct 50 ms 16924 KB Output is correct
5 Correct 210 ms 57048 KB Output is correct
6 Correct 170 ms 58204 KB Output is correct
7 Correct 184 ms 58228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15664 KB Output is correct
2 Correct 269 ms 64912 KB Output is correct
3 Correct 287 ms 64988 KB Output is correct
4 Correct 207 ms 64308 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15664 KB Output is correct
2 Correct 269 ms 64912 KB Output is correct
3 Correct 287 ms 64988 KB Output is correct
4 Correct 207 ms 64308 KB Output is correct
5 Correct 43 ms 16936 KB Output is correct
6 Correct 356 ms 69772 KB Output is correct
7 Correct 230 ms 70372 KB Output is correct
8 Correct 397 ms 71088 KB Output is correct
9 Correct 352 ms 71012 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15668 KB Output is correct
2 Correct 227 ms 55184 KB Output is correct
3 Correct 257 ms 56176 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15668 KB Output is correct
2 Correct 227 ms 55184 KB Output is correct
3 Correct 257 ms 56176 KB Output is correct
4 Correct 50 ms 16904 KB Output is correct
5 Correct 238 ms 59360 KB Output is correct
6 Correct 302 ms 60328 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15672 KB Output is correct
2 Correct 296 ms 64852 KB Output is correct
3 Correct 285 ms 64868 KB Output is correct
4 Correct 232 ms 64216 KB Output is correct
5 Correct 50 ms 16560 KB Output is correct
6 Correct 240 ms 55144 KB Output is correct
7 Correct 273 ms 56040 KB Output is correct
8 Correct 321 ms 54872 KB Output is correct
9 Correct 289 ms 56572 KB Output is correct
10 Correct 348 ms 59620 KB Output is correct
11 Correct 410 ms 57304 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15672 KB Output is correct
2 Correct 296 ms 64852 KB Output is correct
3 Correct 285 ms 64868 KB Output is correct
4 Correct 232 ms 64216 KB Output is correct
5 Correct 50 ms 16560 KB Output is correct
6 Correct 240 ms 55144 KB Output is correct
7 Correct 273 ms 56040 KB Output is correct
8 Correct 321 ms 54872 KB Output is correct
9 Correct 289 ms 56572 KB Output is correct
10 Correct 348 ms 59620 KB Output is correct
11 Correct 410 ms 57304 KB Output is correct
12 Correct 47 ms 16932 KB Output is correct
13 Correct 341 ms 69720 KB Output is correct
14 Correct 298 ms 70372 KB Output is correct
15 Correct 369 ms 71032 KB Output is correct
16 Correct 372 ms 71152 KB Output is correct
17 Correct 52 ms 16944 KB Output is correct
18 Correct 232 ms 59380 KB Output is correct
19 Correct 369 ms 60332 KB Output is correct
20 Correct 342 ms 59472 KB Output is correct
21 Correct 343 ms 61060 KB Output is correct
22 Correct 364 ms 64056 KB Output is correct
23 Correct 343 ms 64416 KB Output is correct
24 Correct 306 ms 62564 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 15632 KB Output is correct
2 Correct 70 ms 19464 KB Output is correct
3 Correct 61 ms 19272 KB Output is correct
4 Correct 76 ms 19344 KB Output is correct
5 Correct 71 ms 17732 KB Output is correct
6 Correct 59 ms 17996 KB Output is correct
7 Correct 47 ms 16564 KB Output is correct
8 Correct 209 ms 54960 KB Output is correct
9 Correct 244 ms 54844 KB Output is correct
10 Correct 44 ms 16628 KB Output is correct
11 Correct 290 ms 64816 KB Output is correct
12 Correct 286 ms 64796 KB Output is correct
13 Correct 219 ms 64248 KB Output is correct
14 Correct 50 ms 16556 KB Output is correct
15 Correct 220 ms 55140 KB Output is correct
16 Correct 257 ms 56036 KB Output is correct
17 Correct 344 ms 54800 KB Output is correct
18 Correct 310 ms 56500 KB Output is correct
19 Correct 330 ms 59576 KB Output is correct
20 Correct 375 ms 57552 KB Output is correct
21 Correct 260 ms 54308 KB Output is correct
22 Correct 220 ms 54740 KB Output is correct
23 Correct 250 ms 55388 KB Output is correct
24 Correct 249 ms 55452 KB Output is correct
25 Correct 290 ms 57268 KB Output is correct
26 Correct 282 ms 55668 KB Output is correct
27 Correct 262 ms 55652 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 15632 KB Output is correct
2 Correct 70 ms 19464 KB Output is correct
3 Correct 61 ms 19272 KB Output is correct
4 Correct 76 ms 19344 KB Output is correct
5 Correct 71 ms 17732 KB Output is correct
6 Correct 59 ms 17996 KB Output is correct
7 Correct 47 ms 16564 KB Output is correct
8 Correct 209 ms 54960 KB Output is correct
9 Correct 244 ms 54844 KB Output is correct
10 Correct 44 ms 16628 KB Output is correct
11 Correct 290 ms 64816 KB Output is correct
12 Correct 286 ms 64796 KB Output is correct
13 Correct 219 ms 64248 KB Output is correct
14 Correct 50 ms 16556 KB Output is correct
15 Correct 220 ms 55140 KB Output is correct
16 Correct 257 ms 56036 KB Output is correct
17 Correct 344 ms 54800 KB Output is correct
18 Correct 310 ms 56500 KB Output is correct
19 Correct 330 ms 59576 KB Output is correct
20 Correct 375 ms 57552 KB Output is correct
21 Correct 260 ms 54308 KB Output is correct
22 Correct 220 ms 54740 KB Output is correct
23 Correct 250 ms 55388 KB Output is correct
24 Correct 249 ms 55452 KB Output is correct
25 Correct 290 ms 57268 KB Output is correct
26 Correct 282 ms 55668 KB Output is correct
27 Correct 262 ms 55652 KB Output is correct
28 Correct 52 ms 16948 KB Output is correct
29 Correct 84 ms 21512 KB Output is correct
30 Correct 71 ms 21388 KB Output is correct
31 Correct 81 ms 21744 KB Output is correct
32 Correct 72 ms 20048 KB Output is correct
33 Correct 65 ms 20084 KB Output is correct
34 Correct 78 ms 16880 KB Output is correct
35 Correct 210 ms 57036 KB Output is correct
36 Correct 175 ms 58248 KB Output is correct
37 Correct 215 ms 58200 KB Output is correct
38 Correct 45 ms 16976 KB Output is correct
39 Correct 341 ms 69772 KB Output is correct
40 Correct 231 ms 70404 KB Output is correct
41 Correct 382 ms 70972 KB Output is correct
42 Correct 362 ms 70960 KB Output is correct
43 Correct 52 ms 16940 KB Output is correct
44 Correct 241 ms 59408 KB Output is correct
45 Correct 300 ms 60260 KB Output is correct
46 Correct 352 ms 59392 KB Output is correct
47 Correct 316 ms 61028 KB Output is correct
48 Correct 349 ms 63924 KB Output is correct
49 Correct 318 ms 64528 KB Output is correct
50 Correct 307 ms 62444 KB Output is correct
51 Correct 225 ms 60144 KB Output is correct
52 Correct 186 ms 59512 KB Output is correct
53 Correct 215 ms 58852 KB Output is correct
54 Correct 187 ms 59432 KB Output is correct
55 Correct 197 ms 59392 KB Output is correct
56 Correct 243 ms 59244 KB Output is correct
57 Correct 288 ms 61500 KB Output is correct
58 Correct 325 ms 60484 KB Output is correct
59 Correct 267 ms 58120 KB Output is correct