oj.uz

Submission #952649

# Submission time Handle Problem Language Result Execution time Memory
952649 2024-03-24T12:49:45 Z Vladth11 Prize (CEOI22_prize) C++14
100 / 100
 3386 ms 395304 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1774 ms 281332 KB Output is correct
2 Correct 1945 ms 281784 KB Output is correct
3 Correct 1018 ms 263716 KB Output is correct
4 Correct 1016 ms 265368 KB Output is correct
5 Correct 1088 ms 268220 KB Output is correct
6 Correct 1650 ms 270764 KB Output is correct
7 Correct 1617 ms 268632 KB Output is correct
8 Correct 1578 ms 266200 KB Output is correct
9 Correct 1016 ms 265240 KB Output is correct
10 Correct 1066 ms 267548 KB Output is correct
11 Correct 991 ms 263748 KB Output is correct
12 Correct 1072 ms 266940 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2102 ms 279752 KB Output is correct
2 Correct 1753 ms 276436 KB Output is correct
3 Correct 1140 ms 263476 KB Output is correct
4 Correct 1139 ms 265604 KB Output is correct
5 Correct 1030 ms 262316 KB Output is correct
6 Correct 1623 ms 265160 KB Output is correct
7 Correct 1873 ms 265472 KB Output is correct
8 Correct 1881 ms 267780 KB Output is correct
9 Correct 1598 ms 268708 KB Output is correct
10 Correct 1576 ms 270808 KB Output is correct
11 Correct 1393 ms 267680 KB Output is correct
12 Correct 1612 ms 272612 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 273128 KB Output is correct
2 Correct 861 ms 274400 KB Output is correct
3 Correct 726 ms 260000 KB Output is correct
4 Correct 716 ms 257752 KB Output is correct
5 Correct 724 ms 256428 KB Output is correct
6 Correct 783 ms 260188 KB Output is correct
7 Correct 789 ms 257664 KB Output is correct
8 Correct 809 ms 261684 KB Output is correct
9 Correct 763 ms 260484 KB Output is correct
10 Correct 784 ms 262468 KB Output is correct
11 Correct 756 ms 266220 KB Output is correct
12 Correct 723 ms 264112 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2312 ms 387912 KB Output is correct
2 Correct 2199 ms 386224 KB Output is correct
3 Correct 1643 ms 357148 KB Output is correct
4 Correct 1626 ms 356884 KB Output is correct
5 Correct 1710 ms 357264 KB Output is correct
6 Correct 1995 ms 362444 KB Output is correct
7 Correct 1989 ms 362420 KB Output is correct
8 Correct 2064 ms 361052 KB Output is correct
9 Correct 1891 ms 361300 KB Output is correct
10 Correct 1991 ms 361484 KB Output is correct
11 Correct 1900 ms 361128 KB Output is correct
12 Correct 1966 ms 361316 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3386 ms 395304 KB Output is correct
2 Correct 3321 ms 394172 KB Output is correct
3 Correct 1914 ms 363140 KB Output is correct
4 Correct 1947 ms 367916 KB Output is correct
5 Correct 1905 ms 363428 KB Output is correct
6 Correct 3121 ms 370848 KB Output is correct
7 Correct 2685 ms 366256 KB Output is correct
8 Correct 2884 ms 368788 KB Output is correct
9 Correct 2544 ms 368900 KB Output is correct
10 Correct 2456 ms 368224 KB Output is correct
11 Correct 2472 ms 368452 KB Output is correct
12 Correct 2594 ms 370204 KB Output is correct