제출 #920635

#제출 시각아이디문제언어결과실행 시간메모리
920635BBart888Railway (BOI17_railway)C++14
0 / 100
161 ms70084 KiB
#include <cstdio> #include <iostream> #include <vector> #include <list> #include <string> #include <set> #include <map> #include <algorithm> #include <fstream> #include <cmath> #include <queue> #include <stack> #include <cassert> #include <cstring> #include <climits> #include <functional> #include <cstdlib> #include <complex> #include <array> #include <iomanip> #include <bitset> #include <unordered_map> #include <random> #define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);} using namespace std; const int MAXN = 2e5 + 111; using ll = long long; const int P = 31; const ll mod1 = 1e9 + 7; const ll mod2 = 998244353; using ld = long double; const ld EPS = 1e-5; using pii = pair<int, int>; typedef complex<ll> Point; const int K = 600; int n, m, k; vector<pair<int,int>> adj[MAXN]; int up[MAXN][20]; int tin[MAXN]; int tout[MAXN]; vector<pair<int, int>> edges; int timer; int dp[MAXN]; set<int> zawiadowca[MAXN]; vector<int> answer; set<int> zabierz[MAXN]; void dfs(int v, int p) { tin[v] = ++timer; up[v][0] = p; for (int i = 1; i < 20; i++) up[v][i] = up[up[v][i - 1]][i - 1]; for (auto u : adj[v]) { if (u.first == p) continue; dfs(u.first, v); } tout[v] = ++timer; } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int a, int b) { if (is_ancestor(a, b)) return a; if (is_ancestor(b, a)) return b; for (int i = 19; i >= 0; i--) { if (!is_ancestor(up[a][i], b)) a = up[a][i]; } return up[a][0]; } void check(int v, int p) { for (auto u : adj[v]) { if (u.first == p) continue; check(u.first, v); //cout <<v<<" => "<< u.first << " " << add[u.first] << '\n'; if (zawiadowca[u.first].size() >= k) { answer.push_back(u.second); //cout << u.second << '\n'; } if (zawiadowca[u.first].size() > zawiadowca[v].size()) { swap(zawiadowca[u.first], zawiadowca[v]); } for (auto x : zawiadowca[u.first]) zawiadowca[v].insert(x); } for (auto x : zabierz[v]) if (zawiadowca[v].find(x) != zawiadowca[v].end()) zawiadowca[v].erase(x); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //fileIO("cardgame"); cin >> n >> m >> k; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; adj[a].push_back({ b ,i}); adj[b].push_back({ a ,i}); edges.push_back({ a,b }); } dfs(1, 1); for (int i = 0; i < m; i++) { int s; cin >> s; int v; vector<int> important; cin >> v; int lc = v; important.push_back(v); for (int f = 1; f < s; f++) { cin >> v; lc = lca(lc, v); important.push_back(v); } for (int f = 0; f < s; f++) { zawiadowca[important[f]].insert(i+1); } zabierz[lc].insert(i+1); } check(1, 1); cout << answer.size() << '\n'; for (auto x : answer) cout << x << " "; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'void check(int, int)':
railway.cpp:99:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |   if (zawiadowca[u.first].size() >= k)
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...