제출 #1369099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369099		pcheloveks	JOI Tour 2 (JOI26_joitour)	C++20	3 / 100	7094 ms	24628 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
 
#include <bits/stdc++.h>
 
#define endl '\n'
 
//#pragma GCC optimize("Ofast")
 
using namespace std;
 
using ll = long long;
using ld = long double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
 
const ll INF = 2e18;
const ll DIM = 100007;
const ll DIMQ = 2007;
const ld PI = 3.1415926535;
const int mod = 998244353;

int n, m, q, timer;
int a[DIM];

int tin[DIM], tout[DIM];
int euler[DIM];

int binJ[20][DIM];

vector < int > v[DIM];

bool isPar(int v1, int v2) {
    return tin[v1] <= tin[v2] && tout[v2] <= tout[v1];
}

int lca(int v1, int v2) {
    if(isPar(v1, v2)) return v1;
    if(isPar(v2, v1)) return v2;

    for(int i = 19; i >= 0; i--) {
        if(!isPar(binJ[i][v1], v2)) v1 = binJ[i][v1];
    }

    return binJ[0][v1];
}

void dfs(int val, int prev) {
    tin[val] = ++timer;
    euler[timer] = val;

    binJ[0][val] = prev;
    for(int p = 1; p < 20; p++) {
        binJ[p][val] = binJ[p - 1][binJ[p - 1][val]]; 
    }

    for(auto to: v[val]) {
        if(to == prev) continue;
        dfs(to, val);
    }

    tout[val] = ++timer;
    euler[timer] = val;
}

struct query {
    int L, R, lca;
};

vector < query > Q;

const int Bsize = 300;

bool cmp(query q1, query q2) {
    if(q1.L / Bsize != q2.L / Bsize) return q1.L < q2.L;
    return q1.R < q2.R;
}

int b[DIMQ];
ll tmpRes[DIMQ], res[DIMQ];

int cnt[DIM];
int cntVer[DIM];

void add(int val) {
    //cout << "+ " << val << endl;
    for(int j = 0; j < q; j++) {
        if(b[j] - val < 0) continue;
        tmpRes[j] += (ll)cnt[b[j] - val];
    }
    cnt[val]++;
}

void del(int val) {
    //cout << "- " << val << endl;
    cnt[val]--;
    for(int j = 0; j < q; j++) {
        if(b[j] - val < 0) continue;
        tmpRes[j] -= (ll)cnt[b[j] - val];
    }
}

void addVer(int val) {
    if(cntVer[val] % 2 == 1) del(a[val]);
    cntVer[val]++;
    if(cntVer[val] % 2 == 1) add(a[val]);
}

void delVer(int val) {
    if(cntVer[val] % 2 == 1) del(a[val]);
    cntVer[val]--;
    if(cntVer[val] % 2 == 1) add(a[val]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
#ifdef IloveCP
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif


    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) {
        int v1, v2;
        cin >> v1 >> v2;

        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }

    timer = 0;
    dfs(1, 1);

    cin >> m;
    for(int i = 1; i <= m; i++) {
        int v1, v2;
        cin >> v1 >> v2;

        int p = lca(v1, v2);

        if(p == v2) swap(v1, v2);

        if(p == v1) {
            Q.push_back({tin[v1], tin[v2], -1});
        }
        else {
            if( tin[v1] <= tin[v2] ) Q.push_back({tout[v1], tin[v2], p});
            else Q.push_back({tout[v2], tin[v1], p});
        }
    }

    sort(Q.begin(), Q.end(), cmp);

    cin >> q;
    for(int i = 0; i < q; i++) cin >> b[i];

    int currL = 1, currR = 1;
    addVer(euler[1]);

    for(int i = 0; i < Q.size(); i++) {
        int L = Q[i].L, R = Q[i].R;

        while(currL > L) addVer(euler[--currL]);
        while(currR < R) addVer(euler[++currR]);

        while(currL < L) delVer(euler[currL++]);
        while(currR > R) delVer(euler[currR--]);

        if(Q[i].lca != -1) addVer(Q[i].lca);
        for(int j = 0; j < q; j++) res[j] += tmpRes[j];
        if(Q[i].lca != -1) delVer(Q[i].lca);
    }

    for(int j = 0; j < q; j++) cout << res[j] << endl;

    return 0;
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 3 / 3
• 서브태스크 2: 0 / 4
• 서브태스크 3: 0 / 5
• 서브태스크 4: 0 / 6
• 서브태스크 5: 0 / 10
• 서브태스크 6: 0 / 7
• 서브태스크 7: 0 / 12
• 서브태스크 8: 0 / 10
• 서브태스크 9: 0 / 15
• 서브태스크 10: 0 / 11
• 서브태스크 11: 0 / 17