oj.uz

답안 #899791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899791 2024-01-07T02:12:46 Z Cookie Traffickers (RMI18_traffickers) C++14
0 / 100
 3500 ms 55392 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, 0, -1, 0};
const int y[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7;
const int mxn = 3e4 + 69, mxq = 1e5 + 5, sq = 500, mxv = 2e7 + 5;
//const int base = (1 <<18);
const int inf = 1e9 + 5, neg = -69420;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int x[9] = {0, 1, 1, -1, -1, 2, -2, 2, -2};
//const inty[9] = {0, 2, -2, 2, -2, 1, 1, -1, -1};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int n, k, q;
vt<int>adj[mxn + 1];
int tin[mxn + 1], tout[mxn + 1], dep[mxn + 1], up[mxn + 1][17], tt = 0;
struct BIT{
    int bit[mxn + 1];
    void upd(int p, int v){
        while(p <= n){
            bit[p] += v; p += p & (-p);
        }
    }
    int get(int p){
        int ans = 0;
        while(p){
            ans += bit[p]; p -= p & (-p);
        }
        return(ans);
    }
};
BIT bit[21][21];
void dfs(int s, int pre){
    tin[s] = ++tt;
    for(auto v: adj[s]){
        if(v != pre){
            up[v][0] = s;  dep[v] = dep[s] + 1;
            dfs(v, s);
        }
    }
    tout[s] = tt;
}
int lca(int u, int v){
    if(dep[u] < dep[v])swap(u, v);
    int k = dep[u] - dep[v];
    forr(i, 0, 17){
        if(k & (1 << i))u = up[u][i];
    }
    if(u == v)return(u);
    dorr(i, 16, 0){
        if(up[u][i] != up[v][i]){
            u = up[u][i]; v = up[v][i];
        }
    }
    return(up[u][0]);
}
void upd(int u, int v, bool type){
    int lc = lca(u, v);
    vt<int>pathu, pathv;


    while(u != lc){

        pathu.pb(u); u = up[u][0];
    }
    while(v != lc){
        pathv.pb(v); v = up[v][0];
    }

    pathu.pb(lc);
    reverse(ALL(pathv));
    for(auto i: pathv)pathu.pb(i);
    int len = sz(pathu);
    assert(len <= 20);
    for(int i = 0; i < sz(pathu); i++){
        //cout << pathu[i] << " " << tin[pathu[i]] << "\n";
        bit[len][i].upd(tin[pathu[i]], 1 * type); bit[len][i].upd(tout[pathu[i]] + 1, -1 * type);
    }

}
ll solve(int u, int v, ll t1,ll t2){
    int lc = lca(u, v);
    ll ans = 0;
    for(int i = 1; i <= 20; i++){
        for(int j = 0; j < i; j++){
            ll cntver = bit[i][j].get(tin[u]) + bit[i][j].get(tin[v]) - bit[i][j].get(tin[lc]) - bit[i][j].get(tin[up[lc][0]]);
            ll cnt = 0;
            for(int tt = t1; tt <= t2; tt++){
                if(tt % i == j)cnt++;
            }
            //cout << cnt << " ";
            ans += cnt * cntver;
        }
    }
    return(ans);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("COLLEGE.INP", "r", stdin);
    //freopen("COLLEGE.OUT", "w", stdout);
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    dfs(1, -1);
    for(int i = 1; i < 16; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    cin >> k;
    for(int i = 0; i < k; i++){
        int u, v; cin >> u >> v;
        upd(u, v, 1);
    }

    cin >> q;
    while(q--){
        int idq; cin >> idq;
        if(idq == 1){
            int u, v; cin >> u >> v; upd(u, v, 1);
        }else if(idq == 2){
            int u, v; cin >> u >> v; upd(u, v, -1);
        }else{
            int u, v, t1, t2; cin >> u >> v >> t1 >> t2;
            cout << solve(u, v, t1, t2) << "\n";
        }

    }

    return(0);
}
/*
6 2
1 2
1 3
1 4
1 5
1 6
2 2
5 6
*/

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 46172 KB Output isn't correct
2 Incorrect 9 ms 50524 KB Output isn't correct
3 Incorrect 8 ms 50524 KB Output isn't correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3562 ms 51764 KB Time limit exceeded
2 Execution timed out 3559 ms 51548 KB Time limit exceeded
3 Execution timed out 3514 ms 52060 KB Time limit exceeded
4 Execution timed out 3571 ms 51804 KB Time limit exceeded
5 Execution timed out 3602 ms 51544 KB Time limit exceeded
6 Execution timed out 3558 ms 51804 KB Time limit exceeded
7 Execution timed out 3530 ms 52212 KB Time limit exceeded
8 Execution timed out 3561 ms 51804 KB Time limit exceeded
9 Execution timed out 3572 ms 52060 KB Time limit exceeded

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3542 ms 54620 KB Time limit exceeded
2 Execution timed out 3517 ms 55128 KB Time limit exceeded
3 Execution timed out 3548 ms 54876 KB Time limit exceeded
4 Execution timed out 3513 ms 54104 KB Time limit exceeded
5 Execution timed out 3560 ms 53964 KB Time limit exceeded
6 Execution timed out 3559 ms 55132 KB Time limit exceeded
7 Execution timed out 3553 ms 55392 KB Time limit exceeded
8 Execution timed out 3538 ms 54932 KB Time limit exceeded