Submission #795405

#	Time	Username	Problem	Language	Result	Execution time	Memory
795405		Sami_Massah	LOSTIKS (INOI20_lostiks)	C++17	0 / 100	76 ms	62164 KiB

Main

#include <bits/stdc++.h>
using namespace std;



const int maxn = 1e6 + 12, lg = 21;
int n, st, en, h[maxn], pe[maxn], par[maxn][lg], kn[maxn], U[maxn], V[maxn];
vector <int> k[maxn], conn[maxn];
vector <int> pos, path, p1, p2, qe, d;
bitset <maxn> marked;
void dfs_set(int u){
    marked[u] = 1;
    for(int i = 0; i + 1 < lg; i++)
        par[u][i + 1] = par[par[u][i]][i];

    for(int e: conn[u]){
        int v = u ^ U[e] ^ V[e];
      //  cout << v << endl;
        if(!marked[v]){
    //        cout << u << "->" << v << endl;
            h[v] = h[u] + 1;
            par[v][0] = u;
            pe[v] = e;
            dfs_set(v);
        }
    }
}
int kpar(int u, int k){
    for(int i = 0; i < k; i++)
        if((k >> i) & 1)
            u = par[u][i];
    return u;
}
int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    a = kpar(a, h[a] - h[b]);
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--)
        if(par[a][i] != par[b][i]){
            a = par[a][i];
            b = par[b][i];
        }
    return par[a][0];
}
pair<int, int> get_path(int a, int b){
    int x = lca(a, b);
  //  cout << a << ' ' << b << ' ' << x << endl;
    int res = 0;
    p1.clear();
    p2.clear();
    while(a != x){
        int e = pe[a];
        int v = par[a][0];
        p1.push_back(e);
        a = v;
        //cout << a << endl;
    }
    while(b != x){
        int e = pe[b];
        int v = par[b][0];
        p2.push_back(e);
        b = v;
    }
    reverse(p2.begin(), p2.end());
    for(int i = 0; i < p2.size(); i++)
        p1.push_back(p2[i]);
    int now = st;
    for(int i: p1){
   //     cout << now << '-' << endl;
        if(kn[i] != 0){
       //     cout << i << "n" << endl;
            d.push_back(now);
            return make_pair(kn[i], i);
            }
        now = now ^ U[i] ^ V[i];
            }
    return make_pair(0, p1.size());
}
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    cin >> st >> en;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b >> kn[i];
        conn[a].push_back(i);
        conn[b].push_back(i);
        U[i] = a;
        V[i] = b;
    }
    dfs_set(1);

   // return 0;
    pos.push_back(en);
    int ans = 0;
    int cnt = 0;
    while(pos.size()){
        cnt += 1;
        if(cnt > 50)
            return 0;
        int x = pos.back();
     /*   for(int j: pos)
            cout << j << ' ';
        cout << endl;
        for(int j: d)
            cout << j << ' ';
        cout << endl;
        cout << st << "->" << x << endl;
        cout << ans << endl;
        cout << endl;
        cout << endl;*/
        auto res = get_path(st, x);
        if(res.first != 0){
            qe.push_back(res.second);
            pos.push_back(res.first);
            continue;
        }
        ans += res.second;
        if(d.size()){
            ans += get_path(x, d.back()).second;
            st = d.back();
            d.pop_back();
        }

        if(qe.size()){
           // cout << qe.back() << '-' << endl;
            kn[qe.back()] = 0;
            qe.pop_back();
            }

        pos.pop_back();

    }
    cout << ans << endl;


}

Compilation message (stderr)

Main.cpp: In function 'std::pair<int, int> get_path(int, int)':
Main.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < p2.size(); i++)
      |                    ~~^~~~~~~~~~~
Main.cpp:50:9: warning: unused variable 'res' [-Wunused-variable]
   50 |     int res = 0;
      |         ^~~

• Subtask 1: 0 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41