oj.uz

Submission #633402

# Submission time Handle Problem Language Result Execution time Memory
633402 2022-08-22T10:43:38 Z keta_tsimakuridze Prize (CEOI22_prize) C++14
100 / 100
 3303 ms 585056 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, tmin[2][N], tmout[2][N], p[2][N][22],  timer= 0, k;
pii q[N][2];
int h[2][N], ans[N][2];
vector<int> x,V[2][N];
bool check(int u, int v, int t) {
    return (tmin[t][u] <= tmin[t][v] && tmin[t][v] <= tmout[t][u]);
}
int lca(int u,int v, int t) {
    if(check(u, v, t)) return u;
    if(check(v, u, t))return v;

    for(int i = 20; i >= 0; i--) {
        if(p[t][u][i] && !check(p[t][u][i], v, t))  u = p[t][u][i];
    }
    return p[t][u][0];
}
void dfs(int u, int t) {
    tmin[t][u] = ++timer;
    if(x.size() < k) x.push_back(u);
    for(int i = 1; i <= 20; i++) p[t][u][i] = p[t][p[t][u][i - 1]][i - 1];
    for(int i = 0; i < V[t][u].size(); i++) p[t][V[t][u][i]][0] = u, dfs(V[t][u][i], t); 
    tmout[t][u] = timer;
}
bool cmp(int x,int y) {
    return (tmin[1][x] < tmin[1][y]);
}
main(){
    int n,  Q, T;
    cin >> n >> k >> Q >> T;
    vector<int> r(2);
    for(int t = 0; t < 2; ++t) {

        for(int i = 1; i <= n; i++) {
            int p;
            cin >> p;
            if(p == -1) r[t] = i;
            else V[t][p].push_back(i);
        }
    }
    dfs(r[0], 0);
    timer = 0;
    dfs(r[1], 1);
    sort(x.begin(), x.end(), cmp);
    
    for(int i = 0; i < x.size(); i++) cout << x[i] << " ";
    cout << endl;
    for(int i = 1; i < x.size(); i++) {
        cout << "? " << x[i - 1] << " " << x[i] << endl;
    }
    cout << "!" << endl; 
    h[0][x[0]] = h[1][x[0]] = 0;
    for(int i = 1; i < x.size(); i++) {
        for(int t = 0; t < 2; t++) {
            cin >> q[i][t].f >> q[i][t].s;
            h[t][lca(x[i - 1], x[i], t)] = h[t][x[i - 1]] - q[i][t].f;
            h[t][x[i]] = h[t][x[i - 1]] - q[i][t].f + q[i][t].s;
        }
    }
    
	
    for(int i = 1; i <= T; i++) {
        int u, v;
        cin >> u >> v;
        for(int t = 0; t < 2; t++) ans[i][t] = h[t][u] + h[t][v] - 2 * h[t][lca(u, v, t)];
    }
    for(int i = 1; i <= T; i++) cout << ans[i][0] << " " << ans[i][1] << endl;

 }

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:26:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   26 |     if(x.size() < k) x.push_back(u);
      |        ~~~~~~~~~^~~
Main.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i < V[t][u].size(); i++) p[t][V[t][u][i]][0] = u, dfs(V[t][u][i], t);
      |                    ~~^~~~~~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:52:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0; i < x.size(); i++) cout << x[i] << " ";
      |                    ~~^~~~~~~~~~
Main.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 1; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~
Main.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 1; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1635 ms 317972 KB Output is correct
2 Correct 1633 ms 318912 KB Output is correct
3 Correct 1273 ms 266276 KB Output is correct
4 Correct 1238 ms 265872 KB Output is correct
5 Correct 1307 ms 266908 KB Output is correct
6 Correct 1680 ms 276564 KB Output is correct
7 Correct 1682 ms 276368 KB Output is correct
8 Correct 1762 ms 276160 KB Output is correct
9 Correct 1240 ms 266120 KB Output is correct
10 Correct 1324 ms 266820 KB Output is correct
11 Correct 1196 ms 265596 KB Output is correct
12 Correct 1258 ms 266580 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1744 ms 318708 KB Output is correct
2 Correct 1548 ms 317312 KB Output is correct
3 Correct 1299 ms 266308 KB Output is correct
4 Correct 1359 ms 266924 KB Output is correct
5 Correct 1349 ms 266516 KB Output is correct
6 Correct 1778 ms 275692 KB Output is correct
7 Correct 1924 ms 276760 KB Output is correct
8 Correct 1849 ms 276848 KB Output is correct
9 Correct 1570 ms 275620 KB Output is correct
10 Correct 1647 ms 275844 KB Output is correct
11 Correct 1576 ms 274600 KB Output is correct
12 Correct 1640 ms 275768 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 307692 KB Output is correct
2 Correct 1361 ms 307764 KB Output is correct
3 Correct 973 ms 256436 KB Output is correct
4 Correct 1041 ms 256512 KB Output is correct
5 Correct 970 ms 256548 KB Output is correct
6 Correct 1190 ms 266440 KB Output is correct
7 Correct 1281 ms 266684 KB Output is correct
8 Correct 1212 ms 266600 KB Output is correct
9 Correct 1116 ms 265060 KB Output is correct
10 Correct 1124 ms 265132 KB Output is correct
11 Correct 1114 ms 265040 KB Output is correct
12 Correct 1128 ms 265108 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3303 ms 571828 KB Output is correct
2 Correct 3301 ms 571824 KB Output is correct
3 Correct 2131 ms 469744 KB Output is correct
4 Correct 2143 ms 469528 KB Output is correct
5 Correct 2220 ms 469532 KB Output is correct
6 Correct 2868 ms 489652 KB Output is correct
7 Correct 2990 ms 489900 KB Output is correct
8 Correct 2972 ms 489988 KB Output is correct
9 Correct 2665 ms 487156 KB Output is correct
10 Correct 2570 ms 487132 KB Output is correct
11 Correct 2546 ms 486940 KB Output is correct
12 Correct 2564 ms 487016 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3156 ms 585056 KB Output is correct
2 Correct 3152 ms 584700 KB Output is correct
3 Correct 2351 ms 480348 KB Output is correct
4 Correct 2380 ms 481668 KB Output is correct
5 Correct 2259 ms 480076 KB Output is correct
6 Correct 3302 ms 501548 KB Output is correct
7 Correct 3089 ms 499836 KB Output is correct
8 Correct 3203 ms 500932 KB Output is correct
9 Correct 2833 ms 497896 KB Output is correct
10 Correct 3002 ms 497352 KB Output is correct
11 Correct 2987 ms 497396 KB Output is correct
12 Correct 2906 ms 498124 KB Output is correct