oj.uz

Submission #773318

# Submission time Handle Problem Language Result Execution time Memory
773318 2023-07-04T21:31:16 Z doowey Prize (CEOI22_prize) C++14
76 / 100
 3500 ms 431904 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 10;
const int LOG = 20;

int n, k;

struct outp{
    int d1, d2, d3, d4;
};

vector<pii> qq;
vector<outp> rr;

struct tree{
    int idx;
    vector<int> T[N];
    int root = -1;
    int tt;
    int tin[N];
    int tout[N];
    int up[LOG][N];
    void dfs(int u, int pa){
        tt ++ ;
        tin[u] = tt;
        up[0][u] = pa;
        for(int ln = 1; ln < LOG; ln ++ ){
            up[ln][u]=up[ln-1][up[ln-1][u]];
        }
        for(auto x : T[u]){
            dfs(x, u);
        }
        tout[u] = tt;
    }
    void input(){
        int p;
        for(int i = 1; i <= n; i ++ ){
            cin >> p;
            if(p == -1) root = i;
            else T[p].push_back(i);
        }
        dfs(root, root);
    }
    bool is_anc(int u, int v){
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }

    int lca(int u, int v){
        if(is_anc(u, v)) return u;
        for(int ln = LOG - 1; ln >= 0 ; ln -- ){
            if(!is_anc(up[ln][u], v)) u = up[ln][u];
        }
        return up[0][u];
    }
    vector<int> lis;
    vector<int> res;
    vector<int> comp;
    void make_queries(vector<int> _s){
        lis = _s;
        sort(lis.begin(), lis.end(), [&](int x, int y){return tin[x] < tin[y];});
        comp = lis;
        for(int i = 0 ;i + 1 < lis.size(); i ++ ){
            res.push_back(qq.size());
            qq.push_back(mp(lis[i], lis[i + 1]));
            comp.push_back(lca(lis[i], lis[i + 1]));
        }
        sort(comp.begin(), comp.end(), [&](int x, int y){return tin[x] < tin[y];});
        comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    }
    vector<int> X[N];
    vector<pii> ss[N]; // dep_v = dep_u + x.se
    int dep[N];
    void add_edge(int u, int v, int w){
        ss[u].push_back(mp(v, w));
        ss[v].push_back(mp(u, -w));
    }
    void f(int u){
        for(auto x : ss[u]){
            if(dep[x.fi] == -1){
                dep[x.fi]=dep[u]+x.se;
                f(x.fi);
            }
        }
    }
    void compute(){
        vector<int> stek;
        for(auto x : comp){
            while(!stek.empty() && is_anc(x, stek.back())) stek.pop_back();
            if(!stek.empty()) X[stek.back()].push_back(x);
            stek.push_back(x);
        }
        int big = stek[0];
        int di, dj;
        for(int i = 0 ; i + 1 < lis.size(); i ++ ){
            int cur = lca(lis[i], lis[i + 1]);
            if(idx == 0){
                di = rr[res[i]].d1;
                dj = rr[res[i]].d2;
            }
            else{
                di = rr[res[i]].d3;
                dj = rr[res[i]].d4;
            }
            add_edge(cur, lis[i], di);
            add_edge(cur, lis[i + 1], dj);
        }
        for(auto x : comp){
            dep[x] = -1;
        }
        dep[big] = 0;
        f(big);
    }
    int get_dist(int i, int j){
        int cur = lca(i, j);
        return dep[i] + dep[j] - 2 * dep[cur];
    }
};

tree ai, bi;

int main(){
    int q, t;
    cin >> n >> k >> q >> t;
    ai.input();
    bi.input();
    ai.idx = 0;
    bi.idx = 1;
    vector<int> pp;
    for(int i = 1; i <= k ; i ++ ){
        pp.push_back(i);
    }
    ai.make_queries(pp);
    bi.make_queries(pp);
    for(auto x : pp) cout << x << " ";
    cout << "\n";
    fflush(stdout);
    for(auto x : qq){
        cout << "? " << x.fi << " " << x.se << "\n";
    }
    cout << "!\n";
    fflush(stdout);
    rr.resize(qq.size());
    for(int i = 0 ; i < qq.size(); i ++ ){
        cin >> rr[i].d1 >> rr[i].d2 >> rr[i].d3 >> rr[i].d4;
    }
    ai.compute();
    bi.compute();
    vector<pii> qwe;
    int u, v;
    for(int it = 1; it <= t; it ++ ){
        cin >> u >> v;
        qwe.push_back(mp(u, v));
    }
    for(auto x : qwe){
        cout << ai.get_dist(x.fi, x.se) << " " << bi.get_dist(x.fi, x.se) << "\n";
    }
    fflush(stdout);
    return 0;
}

Compilation message

Main.cpp: In member function 'void tree::make_queries(std::vector<int>)':
Main.cpp:72:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i = 0 ;i + 1 < lis.size(); i ++ ){
      |                        ~~~~~~^~~~~~~~~~~~
Main.cpp: In member function 'void tree::compute()':
Main.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i = 0 ; i + 1 < lis.size(); i ++ ){
      |                         ~~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for(int i = 0 ; i < qq.size(); i ++ ){
      |                     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1839 ms 292420 KB Output is correct
2 Correct 1731 ms 299168 KB Output is correct
3 Correct 1429 ms 269104 KB Output is correct
4 Correct 1579 ms 267556 KB Output is correct
5 Correct 1820 ms 274148 KB Output is correct
6 Correct 2218 ms 279056 KB Output is correct
7 Correct 2186 ms 278888 KB Output is correct
8 Correct 2147 ms 277124 KB Output is correct
9 Correct 1414 ms 268576 KB Output is correct
10 Correct 1594 ms 272836 KB Output is correct
11 Correct 1289 ms 264876 KB Output is correct
12 Correct 1636 ms 271596 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1825 ms 298516 KB Output is correct
2 Correct 1710 ms 288880 KB Output is correct
3 Correct 1626 ms 268776 KB Output is correct
4 Correct 1739 ms 274764 KB Output is correct
5 Correct 1450 ms 270700 KB Output is correct
6 Correct 1968 ms 272364 KB Output is correct
7 Correct 2333 ms 279836 KB Output is correct
8 Correct 2410 ms 280692 KB Output is correct
9 Correct 2033 ms 279584 KB Output is correct
10 Correct 2103 ms 281508 KB Output is correct
11 Correct 1868 ms 272464 KB Output is correct
12 Correct 2144 ms 281204 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 275320 KB Output is correct
2 Correct 1145 ms 275304 KB Output is correct
3 Correct 835 ms 245376 KB Output is correct
4 Correct 773 ms 245364 KB Output is correct
5 Correct 832 ms 245548 KB Output is correct
6 Correct 1142 ms 252760 KB Output is correct
7 Correct 1062 ms 252788 KB Output is correct
8 Correct 1083 ms 252760 KB Output is correct
9 Correct 1002 ms 250536 KB Output is correct
10 Correct 925 ms 250632 KB Output is correct
11 Correct 936 ms 250544 KB Output is correct
12 Correct 1051 ms 250536 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3272 ms 408688 KB Output is correct
2 Correct 2983 ms 408692 KB Output is correct
3 Correct 1890 ms 351048 KB Output is correct
4 Correct 1887 ms 351088 KB Output is correct
5 Correct 1863 ms 350976 KB Output is correct
6 Correct 2735 ms 365800 KB Output is correct
7 Correct 2891 ms 365976 KB Output is correct
8 Correct 2834 ms 365948 KB Output is correct
9 Correct 2301 ms 361240 KB Output is correct
10 Correct 2418 ms 361236 KB Output is correct
11 Correct 2380 ms 361344 KB Output is correct
12 Correct 2478 ms 361364 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3333 ms 431904 KB Output is correct
2 Correct 3365 ms 430440 KB Output is correct
3 Correct 2390 ms 373460 KB Output is correct
4 Correct 2669 ms 383484 KB Output is correct
5 Correct 2436 ms 371472 KB Output is correct
6 Execution timed out 3579 ms 397012 KB Time limit exceeded
7 Halted 0 ms 0 KB -