제출 #1151546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151546		Issa	Prize (CEOI22_prize)	C++20	0 / 100	1266 ms	360604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e7 + 100;
const ll MOD = 1e9 + 7;
const int maxl = 20;
const ll P = 31;

int n, k, q, t;

struct tree{
    int start = 0;
    int root, t = 0;
    int p[maxl][maxn];
    vector<int> g[maxn];
    vector<pii> e[maxn];
    int tin[maxn], tout[maxn];
    int dep[maxn];

    void dfs(int v){
        tin[v] = ++t;
        for(int k = maxl - 1; k > 0; k--){
            p[k][v] = p[k - 1][p[k - 1][v]];
        } 
        for(int to: g[v]){
            p[0][to] = v;
            dfs(to);
        } tout[v] = t;
    }
    bool ok(int a, int b){
        return tin[a] <= tin[b] && tin[b] <= tout[a];
    }
    int lcm(int a, int b){
        int v = a;
        if(!ok(a, b)){
            for(int k = maxl - 1; k >= 0; k--){
                if(p[k][v] && !ok(p[k][v], b)) v = p[k][v];
            } v = p[0][v];
        } return v;
    }
    void in(){
        for(int i = 1; i <= n; i++){
            int p; cin >> p;
            if(p == -1) root = i;
            else g[p].push_back(i);
        } 
        dfs(root);
    } 
    void add(int a, int b, int c, int d){
        int v = lcm(a, b);
        e[v].push_back({a, c});
        e[v].push_back({b, d});
        e[a].push_back({v, -c});
        e[b].push_back({v, -d});
        if(!start || tin[start] > tin[v]) start = v; 
    }
    void DFS(int v){
        for(auto [to, d]: e[v]){
            if(dep[to] == -1){
                dep[to] = dep[v] + d;
                DFS(to);
            }
        }
    }
    void calc(){
        fill(dep, dep + n + 1, -1);
        dep[start] = 0; DFS(start);
    }
    int get(int a, int b){
        int c = lcm(a, b);
        return dep[a] + dep[b] - 1ll * dep[c] * 2;
    }
} A, B;

void ask(int a, int b){
    cout << "? " << a << ' ' << b << endl;
} 
void calc(int a, int b){
    int a1, a2, b1, b2; 
    cin >> a1 >> a2 >> b1 >> b2;
    A.add(a, b, a1, a2);
    B.add(a, b, b1, b2);
}

void test(){
    cin >> n >> k >> q >> t;
    A.in(); B.in();
    for(int i = 1; i <= k; i++){
        cout << i << ' ';
    } cout << endl;
    for(int i = 1; i < k; i++){
        ask(i, i + 1);
    } for(int i = 1; i < k; i++){
        calc(i, i + 1);
    }
    A.calc();
    B.calc();
    vector<pii> ans;
    while(t--){
        int a, b; cin >> a >> b;
        ans.push_back({A.get(a, b), B.get(a, b)});
    } for(auto [a, b]: ans){
        cout << a << ' ' << b << endl;
    }
} 

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while(t--) test();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24