Submission #952965

#	Time	Username	Problem	Language	Result	Execution time	Memory
952965		Whisper	Railway (BOI17_railway)	C++17	100 / 100	146 ms	74956 KiB

railway

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
const int MAX = 5e5 + 5;

int numNode, numQuery, numNeed;
vector<pair<int, int>> G[MAX];
unordered_map<int, int> cnt[MAX];
vector<int> ans;

int n[MAX];
void dfs(int u, int p, int edgeId){
    for (pair<int, int>&x : G[u]){
        int v = x.first, id = x.second;
        if(v ^ p){
            dfs(v, u, id);
            if ((int)cnt[u].size() < (int)cnt[v].size()) swap(cnt[u], cnt[v]);
            for (auto&[x, c] : cnt[v]){
                cnt[u][x] += c;
                if (cnt[u][x] == n[x]) cnt[u].erase(x);
            }
        }
    }
    if (cnt[u].size() >= numNeed)
        ans.push_back(edgeId);
}
void Whisper(){
    cin >> numNode >> numQuery >> numNeed;
    for(int i = 1; i < numNode; ++i){
        int u, v; cin >> u >> v;
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
    }
    for (int i = 1; i <= numQuery; ++i){
        cin >> n[i];
        for (int v = 1; v <= n[i]; ++v){
            int x; cin >> x;
            cnt[x][i]++;
        }
    }
    dfs(1, 0, 0);
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (int&v : ans) cout << v << ' ';
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(long long int, long long int, long long int)':
railway.cpp:63:23: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   63 |     if (cnt[u].size() >= numNeed)
      |         ~~~~~~~~~~~~~~^~~~~~~~~~

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