oj.uz

Submission #952677

# Submission time Handle Problem Language Result Execution time Memory
952677 2024-03-24T13:33:46 Z Vladth11 Prize (CEOI22_prize) C++14
100 / 100
 2948 ms 387032 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 = 19;
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
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
    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:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for(int i = 0; i < chosen.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i = 0; i < chosen.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:121:18: warning: unused variable 'rt1' [-Wunused-variable]
  121 |     int k, q, t, rt1 = 0, rt2 = 0;
      |                  ^~~
Main.cpp:121:27: warning: unused variable 'rt2' [-Wunused-variable]
  121 |     int k, q, t, rt1 = 0, rt2 = 0;
      |                           ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1567 ms 253260 KB Output is correct
2 Correct 1783 ms 256060 KB Output is correct
3 Correct 854 ms 239652 KB Output is correct
4 Correct 832 ms 238676 KB Output is correct
5 Correct 931 ms 243032 KB Output is correct
6 Correct 1506 ms 242904 KB Output is correct
7 Correct 1411 ms 242092 KB Output is correct
8 Correct 1424 ms 241948 KB Output is correct
9 Correct 876 ms 239448 KB Output is correct
10 Correct 876 ms 240888 KB Output is correct
11 Correct 756 ms 237868 KB Output is correct
12 Correct 846 ms 240956 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1875 ms 256004 KB Output is correct
2 Correct 1535 ms 252320 KB Output is correct
3 Correct 832 ms 239612 KB Output is correct
4 Correct 954 ms 242808 KB Output is correct
5 Correct 876 ms 240324 KB Output is correct
6 Correct 1419 ms 240452 KB Output is correct
7 Correct 1628 ms 243228 KB Output is correct
8 Correct 1653 ms 245564 KB Output is correct
9 Correct 1323 ms 244040 KB Output is correct
10 Correct 1330 ms 245032 KB Output is correct
11 Correct 1233 ms 241808 KB Output is correct
12 Correct 1361 ms 246260 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 246840 KB Output is correct
2 Correct 727 ms 246200 KB Output is correct
3 Correct 557 ms 233316 KB Output is correct
4 Correct 543 ms 232172 KB Output is correct
5 Correct 550 ms 233520 KB Output is correct
6 Correct 656 ms 233796 KB Output is correct
7 Correct 700 ms 233844 KB Output is correct
8 Correct 641 ms 233516 KB Output is correct
9 Correct 598 ms 234416 KB Output is correct
10 Correct 668 ms 234556 KB Output is correct
11 Correct 623 ms 234216 KB Output is correct
12 Correct 663 ms 234376 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1955 ms 378348 KB Output is correct
2 Correct 1852 ms 378464 KB Output is correct
3 Correct 1393 ms 349128 KB Output is correct
4 Correct 1346 ms 349136 KB Output is correct
5 Correct 1379 ms 349132 KB Output is correct
6 Correct 1704 ms 353120 KB Output is correct
7 Correct 1752 ms 353032 KB Output is correct
8 Correct 1682 ms 353368 KB Output is correct
9 Correct 1593 ms 353728 KB Output is correct
10 Correct 1605 ms 353740 KB Output is correct
11 Correct 1563 ms 353420 KB Output is correct
12 Correct 1601 ms 353552 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2948 ms 387032 KB Output is correct
2 Correct 2948 ms 386440 KB Output is correct
3 Correct 1550 ms 355724 KB Output is correct
4 Correct 1638 ms 359244 KB Output is correct
5 Correct 1554 ms 354764 KB Output is correct
6 Correct 2757 ms 362884 KB Output is correct
7 Correct 2477 ms 358948 KB Output is correct
8 Correct 2563 ms 360856 KB Output is correct
9 Correct 2188 ms 361528 KB Output is correct
10 Correct 2146 ms 360776 KB Output is correct
11 Correct 2125 ms 361176 KB Output is correct
12 Correct 2254 ms 362636 KB Output is correct