oj.uz

Submission #966894

# Submission time Handle Problem Language Result Execution time Memory
966894 2024-04-20T14:59:21 Z efedmrlr Prize (CEOI22_prize) C++17
0 / 100
 2736 ms 613288 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 2147483600;
const int N = 1e6 + 5;
const int ALPH = 26;
const int LGN = 21;
constexpr int MOD = 1e9+7;
int n,m,q,t;

vector<vector<int> > adj1(N, vector<int>()), adj2(N, vector<int>());
int r1, r2;
vector<int> sub2, sub1;

vector<array<int,3> > pt1, pt2;
vector<vector<int> > anc1(N, vector<int>(LGN, 0)), anc2(N, vector<int>(LGN, 0));
vector<int> dep1(N, 0), dep2(N, 0);
vector<int> d1(N, INF), d2(N, INF);
void calc(vector<vector<int> > &anc) {
    for(int k = 1; k < LGN; k++) {
        for(int i = 1; i <=n; i++) {
            anc[i][k] = anc[anc[i][k - 1]][k - 1];
        }
    }
}
int kth_anc(int x, int k, vector<vector<int> > &anc) {
    for(int i = 0; i < LGN; i++) {
        if(k & (1 << i)) {
            x = anc[x][i];
        }
    }
    return x;
}

int lca(int a, int b, vector<vector<int> > &anc, vector<int> &dep) {
    if(dep[a] > dep[b]) swap(a, b);
    b = kth_anc(b, dep[b] - dep[a], anc);
    if(a == b) return a;
    for(int i = LGN - 1; i>=0; i--) {
        if(anc[a][i] != anc[b][i]) {
            a = anc[a][i]; b = anc[b][i];
        }
    }
    return anc[a][0];
}

void dfs(int node, vector<int> &ord, vector<vector<int> > &adj, vector<int> &dep) {
    ord.pb(node);
    for(auto c : adj[node]) {
        dep[c] = dep[node]  + 1;
        dfs(c, ord, adj, dep);
    }
} 
void get_d(int node, vector<vector<array<int,2> > > &adj, vector<int> &d) {
    for(auto &c : adj[node]) {
        if(d[c[0]] != INF) continue;
        d[c[0]] = d[node] + c[1]; 
        get_d(c[0], adj, d);
    }
}
inline void solve() {
    cin>>n>>m>>q>>t;
    for(int i = 1; i<=n; i++) {
        cin >> anc1[i][0];
        if(anc1[i][0] == -1) {
            anc1[i][0] = i;
            r1 = i;
        }
        else {
            adj1[anc1[i][0]].pb(i);
        }
    }
    for(int i = 1; i<=n; i++) {
        cin >> anc2[i][0];
        if(anc2[i][0] == -1) {
            anc2[i][0] = i;
            r2 = i;
        }
        else {
            adj2[anc2[i][0]].pb(i);
        }
    }
    vector<int> ord;
    dfs(r1, ord, adj1, dep1);
    for(int i = 0; i < m; i++) {
        sub2.pb(ord[i]);
        cout << ord[i] << " ";
    }
    cout.flush();
    ord.clear();
    dfs(r2, ord, adj2, dep2);
    vector<int> tmp(n + 3);
    calc(anc1);
    calc(anc2);
    for(int i = 0; i < n; i++) {
        tmp[ord[i]] = i;
    }
    sub1 = sub2;
    sort(all(sub2), [&tmp](int a, int b) {
        return tmp[a] < tmp[b];
    });
    for(int i = 1; i < m; i++) {
        cout << "? " << sub2[i - 1] << " " << sub2[i] << "\n";
    }
    cout.flush();
    r2 = sub2[0];
    for(int i = 1; i < m; i++) {
        array<int,4> x;
        REP(j, 4) cin >> x[j];
        int lc = lca(sub2[i - 1], sub2[i], anc1, dep1);
        pt1.pb({sub2[i - 1], lc, x[0]});
        pt1.pb({sub2[i], lc, x[1]});
        lc = lca(sub2[i - 1], sub2[i], anc2, dep2);
        sub2.pb(lc);
        if(dep2[lc] < dep2[r2]) {
            r2 = lc;
        }
        pt2.pb({sub2[i - 1], lc, x[2]});
        pt2.pb({sub2[i], lc, x[3]});
    }
    sort(all(sub2), [&tmp](int a, int b) {
        return tmp[a] < tmp[b];
    });
    vector<vector<array<int,2> > > ad1(n + 3, vector<array<int,2> >()), ad2(n + 3, vector<array<int,2> >());
    sub2.resize(unique(all(sub2)) - sub2.begin());
    for(auto &c : pt1) {
        ad1[c[0]].pb({c[1], -c[2]});
        ad1[c[1]].pb({c[0], c[2]});
    }
    for(auto &c : pt2) {
        ad2[c[0]].pb({c[1], -c[2]});
        ad2[c[1]].pb({c[0], c[2]});
    }
    d1[r1] = d2[r2] = 0;
    get_d(r1, ad1, d1);
    get_d(r2, ad2, d2);
    vector<array<int,2> > que(t);
    // cout << "nodes:\n";
    // for(int i : sub1) {
    //     cout << i << " " << d1[i] << "\n";
    // }
    // cout << "\n";
    // cout << "nodes2:\n";
    // for(int i : sub2) {
    //     cout << i << " " << d2[i] << "\n";   
    // }
    // cout << "\n";


    REP(z, t) {
        cin >> que[z][0] >> que[z][1];
    }
    for(auto &c : que) {
        cout << d1[c[0]] + d1[c[1]] - 2 * d1[lca(c[0], c[1], anc1, dep1)];
        cout << " ";
        cout << d2[c[0]] + d2[c[1]] - 2 * d2[lca(c[0], c[1], anc2, dep2)];
        cout << "\n";
    }
    cout.flush();
}
 
signed main() {

    // fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1404 ms 542248 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1275 ms 542608 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1236 ms 540624 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2649 ms 611000 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2736 ms 613288 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -