oj.uz

Submission #952648

# Submission time Handle Problem Language Result Execution time Memory
952648 2024-03-24T12:45:26 Z Vladth11 Prize (CEOI22_prize) C++14
100 / 100
 3399 ms 395836 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 1000001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;

int n;

class Tree{
public:
    vector <int> v[NMAX];
    int dp[nrbits + 1][NMAX];
    vector <int> preorder;
    pii timp[NMAX];
    int stamp, root;
    void init(){
        preorder.clear();
        stamp = root = 0;
        for(int i = 0; i <= n; i++){
            v[i].clear();
            timp[i].first = timp[i].second = 0;
        }
        for(int j = 0; j <= nrbits; j++){
            for(int i = 0; i <= n; i++)
                dp[j][i] = 0;
        }
    }
    bool isParent(int a, int b){
        return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
    }
    int LCA(int a, int b){
        int r = a, pas = nrbits;
        while(pas >= 0){
            int nxt = dp[pas][r];
            if(nxt != 0 && !isParent(nxt, b)){
                r = nxt;
            }
            pas--;
        }
        if(!isParent(r, b))
            r = dp[0][r];
        return r;
    }
    void setFather(int a, int b){
        if(a == -1){
            root = b;
            return;
        }
        v[b].push_back(a);
        v[a].push_back(b);
    }
    void DFS(int node, int p){
        preorder.push_back(node);
        timp[node].first = ++stamp;
        dp[0][node] = p;
        for(auto x : v[node]){
            if(x == p) continue;
            DFS(x, node);
        }
        timp[node].second = stamp;
    }
    void prec(){
        for(int j = 1; j <= nrbits; j++){
            for(int i = 1; i <= n; i++){
                dp[j][i] = dp[j - 1][dp[j - 1][i]];
            }
        }
    }
}arb1, arb2;

class DSU{ /// Momentan DSU doar cu numele
public:
   vector <pii> v[NMAX];
   int dist[NMAX];
    void init(){
        for(int i = 1; i <= n; i++){
            v[i].clear();
            dist[i] = 2e9;
        }
    }
    void setDistance(int a, int b, int c){
        v[a].push_back({b, c});
        v[b].push_back({a, -c});
    }
    void DFS(int node){
        for(auto x : v[node]){
            if(dist[x.first] == 2e9){
                dist[x.first] = x.second + dist[node];
                DFS(x.first);
            }
        }
    }
    void baga(int x){
        dist[x] = 0;
        DFS(x);
    }
}dsu1, dsu2;

pii sol[NMAX];

bool cmp(int a, int b){
    return arb2.timp[a].first < arb2.timp[b].first;
}

signed main() {
#ifdef HOME
  //  ifstream cin(".in");
   // ofstream cout(".out");
#endif // HOME
    int k, q, t, rt1 = 0, rt2 = 0;
    cin >> n >> k >> q >> t;
    arb1.init();
    arb2.init();
    dsu1.init();
    dsu2.init();
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        arb1.setFather(p, i);
    }
    for(int i = 1; i <= n; i++){
        int p;
        cin >> p;
        arb2.setFather(p, i);
    }
    arb1.DFS(arb1.root, 0);
    arb2.DFS(arb2.root, 0);
    arb1.prec();
    arb2.prec();

    vector <int> chosen;
    for(int i = 0; i < k; i++){
        chosen.push_back(arb1.preorder[i]);
    }
    for(auto x : chosen){
        cout << x << " ";
    }
    cout << "\n";
    sort(chosen.begin(), chosen.end(), cmp);
    for(int i = 0; i < chosen.size() - 1; i++){
        cout << "? " << chosen[i] << " " << chosen[i + 1] << "\n";
    }
    cout << "!" << endl;
    int minim = 2e9;
    int cine = 0;
    for(int i = 0; i < chosen.size() - 1; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int lca1 = arb1.LCA(chosen[i], chosen[i + 1]);
        int lca2 = arb2.LCA(chosen[i], chosen[i + 1]);
        if(arb2.timp[lca2].first < minim){
            minim = arb2.timp[lca2].first;
            cine = lca2;
        }
        dsu1.setDistance(lca1, chosen[i], a);
        dsu1.setDistance(lca1, chosen[i + 1], b);
        dsu2.setDistance(lca2, chosen[i], c);
        dsu2.setDistance(lca2, chosen[i + 1], d);
    }
    dsu1.baga(arb1.root);
    dsu2.baga(cine);
    for(int i = 0; i < t; i++){
        int a, b;
        cin >> a >> b;
        int lca1 = arb1.LCA(a, b);
        int lca2 = arb2.LCA(a, b);
        sol[i] = {dsu1.dist[a] - 2 * dsu1.dist[lca1] + dsu1.dist[b], dsu2.dist[a] - 2 * dsu2.dist[lca2] + dsu2.dist[b]};
    }
    for(int i = 0; i < t; i++){
        cout << sol[i].first << " " << sol[i].second << "\n";
    }
    cout << endl;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for(int i = 0; i < chosen.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i = 0; i < chosen.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:120:18: warning: unused variable 'rt1' [-Wunused-variable]
  120 |     int k, q, t, rt1 = 0, rt2 = 0;
      |                  ^~~
Main.cpp:120:27: warning: unused variable 'rt2' [-Wunused-variable]
  120 |     int k, q, t, rt1 = 0, rt2 = 0;
      |                           ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1778 ms 260152 KB Output is correct
2 Correct 2012 ms 262648 KB Output is correct
3 Correct 1044 ms 248460 KB Output is correct
4 Correct 1048 ms 246048 KB Output is correct
5 Correct 1083 ms 250308 KB Output is correct
6 Correct 1701 ms 249096 KB Output is correct
7 Correct 1691 ms 251028 KB Output is correct
8 Correct 1560 ms 248768 KB Output is correct
9 Correct 1002 ms 247892 KB Output is correct
10 Correct 1126 ms 252176 KB Output is correct
11 Correct 981 ms 246796 KB Output is correct
12 Correct 1057 ms 251368 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2224 ms 265568 KB Output is correct
2 Correct 1760 ms 261020 KB Output is correct
3 Correct 1018 ms 249796 KB Output is correct
4 Correct 1086 ms 250784 KB Output is correct
5 Correct 1124 ms 251308 KB Output is correct
6 Correct 1655 ms 247048 KB Output is correct
7 Correct 1867 ms 250284 KB Output is correct
8 Correct 1874 ms 250748 KB Output is correct
9 Correct 1576 ms 252732 KB Output is correct
10 Correct 1635 ms 251856 KB Output is correct
11 Correct 1470 ms 248432 KB Output is correct
12 Correct 1600 ms 251740 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 255388 KB Output is correct
2 Correct 897 ms 255064 KB Output is correct
3 Correct 752 ms 240524 KB Output is correct
4 Correct 681 ms 239144 KB Output is correct
5 Correct 728 ms 239052 KB Output is correct
6 Correct 811 ms 240596 KB Output is correct
7 Correct 792 ms 240600 KB Output is correct
8 Correct 813 ms 241104 KB Output is correct
9 Correct 753 ms 243212 KB Output is correct
10 Correct 759 ms 241292 KB Output is correct
11 Correct 750 ms 242648 KB Output is correct
12 Correct 760 ms 242808 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2251 ms 386220 KB Output is correct
2 Correct 2204 ms 386744 KB Output is correct
3 Correct 1721 ms 357304 KB Output is correct
4 Correct 1654 ms 357088 KB Output is correct
5 Correct 1672 ms 356960 KB Output is correct
6 Correct 2082 ms 360840 KB Output is correct
7 Correct 2079 ms 362592 KB Output is correct
8 Correct 2041 ms 361012 KB Output is correct
9 Correct 1974 ms 362928 KB Output is correct
10 Correct 2005 ms 363244 KB Output is correct
11 Correct 1963 ms 361364 KB Output is correct
12 Correct 1909 ms 362772 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3399 ms 394868 KB Output is correct
2 Correct 3311 ms 395836 KB Output is correct
3 Correct 1922 ms 362968 KB Output is correct
4 Correct 2029 ms 366544 KB Output is correct
5 Correct 1862 ms 362296 KB Output is correct
6 Correct 3168 ms 370936 KB Output is correct
7 Correct 2856 ms 366564 KB Output is correct
8 Correct 2966 ms 368956 KB Output is correct
9 Correct 2633 ms 369580 KB Output is correct
10 Correct 2466 ms 368372 KB Output is correct
11 Correct 2562 ms 368752 KB Output is correct
12 Correct 2558 ms 371704 KB Output is correct