Submission #879657

#	Time	Username	Problem	Language	Result	Execution time	Memory
879657		Karoot	Railway (BOI17_railway)	C++17	7 / 100	144 ms	48340 KiB

railway

#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

typedef long long ll;

ll linf = 1e15+1;

using namespace std;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 1e5+1;
set<pair<int, int> > s[MAXN];
int wutS[MAXN];
vector<int> children[MAXN];
int n, m, k;
int q = 0;
vector<pair<int, int>> adj[MAXN];
int nodeId[MAXN], binPar[MAXN][20];
vector<pair<int, int> > elemsNode[MAXN];
vector<pair<int, int>> ans;
int depthNode[MAXN];

void rootTree(int node, int parent, int depth){
    depthNode[node] = depth;
    //cout << node << " " << parent << " " << depth << " " << binPar[node][0] << endl;
    for (auto& e : adj[node]){
        if (e.first != parent){
            children[node].push_back(e.first);
            nodeId[e.first] = e.second;
            binPar[e.first][0] = node;
            rootTree(e.first, node, depth+1);
        }
    }
}

void smallerToLarger(int node, int depth){
    if (children[node].size() == 0){
        wutS[node] = q;
        for (auto& e : elemsNode[node]){
            if (depth+1 != e.first)s[q].insert(e);
        }
        ans.push_back({s[q].size(), node});
        q++;

        /*cout << "LO " << node << " " << wutS[node] << endl;
        for (auto& e : s[wutS[node]]){
            cout << e.first << "," << e.second << "   "; 
        }
        cout << endl << endl;*/
        
        return;
    }
    int maxiChild = -1, maxi = -1;
    for (auto& e : children[node]){
        smallerToLarger(e, depth+1);
        //cout << e << ": " << node << ": " << wutS[e] << " " << (*s[wutS[e]].begin()).first << " " << (*s[wutS[e]].begin()).first << " " << s[wutS[e]].size() << endl;
        int sZ = s[wutS[e]].size();
        if (sZ > maxi){
            //cout << "should be here" << endl;
            maxiChild = e;
            maxi = s[wutS[e]].size();
        }
    }

    //cout << node << " _ " << maxiChild << endl;

    wutS[node] = wutS[maxiChild];
    for (auto& e : children[node]){
        if (e != maxiChild){
            for (auto& l : s[wutS[e]]){
                if (l.first != depth+1) s[wutS[node]].insert(l);
            }
        }
    }

    
    for (auto& e : elemsNode[node]){
        if (depth+1 != e.first)s[wutS[node]].insert(e);
    }

    /*cout << "Ye1 " << node << " " << wutS[node] << endl;
    for (auto& e : s[wutS[node]]){
        cout << e.first << "," << e.second << "   "; 
    }
    cout << endl << endl;*/

    while (true){
        auto it = s[wutS[node]].lower_bound({depth, 0});
        if (it == s[wutS[node]].end())break;
        s[wutS[node]].erase(it);
    }


    /*cout << "Ye2 " << node << " " << wutS[node] << endl;
    for (auto& e : s[wutS[node]]){
        cout << e.first << "," << e.second << "   "; 
    }
    cout << endl << endl;*/


    ans.push_back({s[wutS[node]].size(), node});
    
    return;
}


void initBinPar(){
    binPar[0][0] = 0;
    for (int j = 1; j < 20; j++){
        for (int i = 0; i < n; i++){
            binPar[i][j] = binPar[binPar[i][j-1]][j-1];
        }
    }
    return;
}

int jump(int node, int x){
    for (int i = 20; i >= 0; i--){
        if (x & (1<<i))node = binPar[node][i];
    }
    return node;
}

int lca(vector<int> v){
    int miniD = 1e7;
    for (auto e : v){
        miniD = min(miniD, depthNode[e]);
    }
    for (int i = 0; i < v.size(); i++){
        v[i] = jump(v[i], depthNode[v[i]]-miniD);
    }

    bool isAllSame = true;
    for (int i = 0; i < v.size(); i++){
        if (v[i] != v[0])isAllSame = false;
    }
    if (isAllSame)return miniD;

    for (int i = 20; i >= 0; i--){
        bool works = true;
        int firstVal = binPar[v[0]][i];
        for (int x : v){
            if (binPar[x][i] != firstVal)works = false;
        }
        if (!works){
            for (int j = 0; j < v.size(); j++){
                v[j] = binPar[v[j]][i];
            }
        }
    }
    return depthNode[binPar[v[0]][0]];
}
int main(){
    scoobydoobydoo();
    cin >> n >> m >> k;
    for (int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].push_back({b, i+1});
        adj[b].push_back({a, i+1});
    }

    rootTree(0, 0, 0);
    initBinPar();

    /*for (int i = 0; i < n; i++){
        cout << "N" << i << ": " << nodeId[i] << " ";
    }
    cout << endl; */   

    for (int i = 0; i < m; i++){
        int l; cin >> l;
        vector<int> v;
        for (int j = 0; j < l; j++){
            int t; cin >> t;
            v.push_back(--t);
        }
        int d = lca(v);
        //cout << d << endl;
        for (int x : v){
            elemsNode[x].push_back({d, i});
        }
    }


    /*for (int i = 0; i < n; i++){
        cout << i << ": ";
        for (auto& e : elemsNode[i]){
            cout << e.first << ", " << e.second << "  ";
        }
        cout << endl;
    }*/


    smallerToLarger(0, 0);

    /*for (int i = 0; i <= q; i++){
        cout << i << ": ";
        for (auto& e : s[i]){
            cout << e.first << ", " << e.second << "  ";
        }
        cout << endl;
    }*/

    sort(rall(ans));

    vector<int> nAns;
    for (int i = 0; i < ans.size() && ans[i].first >= k; i++){
        //cout << ans[i].first << " " << ans[i].second << ";  ";
        nAns.push_back(nodeId[ans[i].second]);
    }
    //cout << endl;

    sort(all(nAns));

    cout << nAns.size() << endl;
    for (auto& e : nAns){
        cout << e << " ";
    }
    cout << endl;



    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int lca(std::vector<int>)':
railway.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i = 0; i < v.size(); i++){
      |                     ~~^~~~~~~~~~
railway.cpp:150:23: 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 < v.size(); i++){
      |                     ~~^~~~~~~~~~
railway.cpp:162:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             for (int j = 0; j < v.size(); j++){
      |                             ~~^~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:224:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for (int i = 0; i < ans.size() && ans[i].first >= k; i++){
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 7 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25