Submission #1095406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095406		quanlt206	Railway (BOI17_railway)	C++17	100 / 100	169 ms	45140 KiB

railway

#include<bits/stdc++.h>
#define X first
#define Y second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, b, a) for(int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define mxx max_element
#define mnn min_element
#define SQR(x) (1LL * (x) * (x))
#define MASK(i) (1LL << (i))
#define Point Vector
#define left Left
#define right Right
#define div Div

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }

/* END OF TEMPLATE */

const int N = 1e5 + 7;


int P[N][20], high[N];

int n, m, k;

int last_edge[N];

vector<pii> v[N];

map<int, int> mp[N];

void dfs(int x, int par) {
    P[x][0] = par;
    for (int i = 1; i < 18; i++) P[x][i] = P[P[x][i - 1]][i - 1];
    for (auto y : v[x])
        if (y.X != par) {
            high[y.X] = high[x] + 1;
            last_edge[y.X] = y.Y;
            dfs(y.X, x);
        }
}

int LCA(int u, int v) {
    if (high[u] > high[v]) swap(u, v);
    int h = high[v] - high[u];
    for (int i = 0; i < 18; i++)
        if (h & MASK(i)) v = P[v][i];
    if (u == v) return u;
    for (int i = 17; i >= 0; i--)
        if (P[u][i] != P[v][i]) u = P[u][i], v = P[v][i];
    return P[u][0];
}

void update(int x, int y, int w) {
    mp[x][w]++;
    mp[y][w]++;
    mp[LCA(x, y)][w]-=2;
}

vector<int> res;

void DFS(int x, int par) {
    for (auto y : v[x])
        if (y.X != par) {
            DFS(y.X, x);
            if ((int)mp[x].size() < (int)mp[y.X].size()) swap(mp[x], mp[y.X]);
            for (auto tmp : mp[y.X]) {
                mp[x][tmp.X]+=tmp.Y;
                if (mp[x][tmp.X] == 0) mp[x].erase(mp[x].find(tmp.X));
            }
        }
    if (mp[x].size() >= k) res.push_back(last_edge[x]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin>>x>>y;
        v[x].push_back({y, i});
        v[y].push_back({x, i});
    }
    dfs(1, 1);
    for (int t = 1; t <= m; t++) {
        int s;
        cin>>s;
        set<int> tmp;
        while (s--) {
            int x;
            cin>>x;
            tmp.insert(x);
        }
        vector<int> a(tmp.begin(), tmp.end());
        for (int i = 1; i < a.size(); i++) update(a[i - 1], a[i], t);
    }
    DFS(1, 1);
    sort(all(res));
    cout<<res.size()<<"\n";
    for (auto x : res) cout<<x<<" ";
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void DFS(int, int)':
railway.cpp:96:22: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |     if (mp[x].size() >= k) res.push_back(last_edge[x]);
      |         ~~~~~~~~~~~~~^~~~
railway.cpp: In function 'int main()':
railway.cpp:120:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for (int i = 1; i < a.size(); i++) update(a[i - 1], a[i], t);
      |                         ~~^~~~~~~~~~

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