oj.uz

Submission #952676

# Submission time Handle Problem Language Result Execution time Memory
952676 2024-03-24T13:30:25 Z Vladth11 Prize (CEOI22_prize) C++14
100 / 100
 2991 ms 394896 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
  	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 1743 ms 256904 KB Output is correct
2 Correct 1914 ms 258272 KB Output is correct
3 Correct 891 ms 241892 KB Output is correct
4 Correct 927 ms 241388 KB Output is correct
5 Correct 903 ms 243464 KB Output is correct
6 Correct 1520 ms 244392 KB Output is correct
7 Correct 1482 ms 244176 KB Output is correct
8 Correct 1534 ms 243664 KB Output is correct
9 Correct 854 ms 241644 KB Output is correct
10 Correct 891 ms 243560 KB Output is correct
11 Correct 843 ms 240360 KB Output is correct
12 Correct 896 ms 243144 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1926 ms 258484 KB Output is correct
2 Correct 1757 ms 253924 KB Output is correct
3 Correct 893 ms 241972 KB Output is correct
4 Correct 968 ms 244800 KB Output is correct
5 Correct 912 ms 242904 KB Output is correct
6 Correct 1493 ms 242420 KB Output is correct
7 Correct 1707 ms 245880 KB Output is correct
8 Correct 1750 ms 246000 KB Output is correct
9 Correct 1407 ms 246672 KB Output is correct
10 Correct 1529 ms 247684 KB Output is correct
11 Correct 1274 ms 244096 KB Output is correct
12 Correct 1448 ms 247288 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 248684 KB Output is correct
2 Correct 733 ms 248872 KB Output is correct
3 Correct 608 ms 234468 KB Output is correct
4 Correct 611 ms 234376 KB Output is correct
5 Correct 580 ms 233932 KB Output is correct
6 Correct 699 ms 236316 KB Output is correct
7 Correct 681 ms 236212 KB Output is correct
8 Correct 678 ms 235724 KB Output is correct
9 Correct 641 ms 236072 KB Output is correct
10 Correct 663 ms 236256 KB Output is correct
11 Correct 636 ms 236912 KB Output is correct
12 Correct 656 ms 236224 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2037 ms 387332 KB Output is correct
2 Correct 1998 ms 386172 KB Output is correct
3 Correct 1375 ms 357016 KB Output is correct
4 Correct 1413 ms 356968 KB Output is correct
5 Correct 1423 ms 357384 KB Output is correct
6 Correct 1769 ms 360860 KB Output is correct
7 Correct 1834 ms 361040 KB Output is correct
8 Correct 1720 ms 360864 KB Output is correct
9 Correct 1674 ms 361576 KB Output is correct
10 Correct 1719 ms 361304 KB Output is correct
11 Correct 1674 ms 361360 KB Output is correct
12 Correct 1641 ms 361332 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2991 ms 394896 KB Output is correct
2 Correct 2962 ms 394300 KB Output is correct
3 Correct 1564 ms 362824 KB Output is correct
4 Correct 1702 ms 367164 KB Output is correct
5 Correct 1586 ms 362760 KB Output is correct
6 Correct 2747 ms 371136 KB Output is correct
7 Correct 2471 ms 367096 KB Output is correct
8 Correct 2662 ms 369432 KB Output is correct
9 Correct 2289 ms 369172 KB Output is correct
10 Correct 2157 ms 368672 KB Output is correct
11 Correct 2132 ms 368452 KB Output is correct
12 Correct 2239 ms 370724 KB Output is correct