| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 878289 |
2023-11-24T07:59:29 Z |
vjudge1 |
Martian DNA (BOI18_dna) |
C++17 |
|
65 ms |
104276 KB |
// in the name of God
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define int long long
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define GCD(a, b) __gcd(a, b)
#define maxl *max_element
#define minl *min_element
#define ff first
#define ss second
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define mmt make_pair
#define endl '\n'
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O4")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 9, maxn = 2e5 + 10, inf = 1e18 + 1, lg = 25, pp = 4447, modd = 1e9 + 9;
int h[maxn], cnt[maxn] = {}, n, m, k;
map<pair<int, int>, int> mp;
vector<vector<int>> g(maxn), par(maxn, vector<int>(lg, -1));
set<int> ans;
void dfs(int v, int p = -1){
if(v != 0){
par[v][0] = p;
for(int i = 1; i < lg; ++i){
if(par[v][i - 1] != -1) par[v][i] = par[par[v][i - 1]][i - 1];
}
}
for(int u : g[v]){
if(u != p){
h[u] = h[v] + 1;
dfs(u, v);
}
}
}
void dfs2(int v, int p = -1){
for(int u : g[v]){
if(u != p){
dfs(u, v);
if(cnt[u] >= k) ans.insert(mp[mmt(u, v)]);
cnt[v] += cnt[u];
}
}
}
int lca(int v, int u){
if(v == u) return v;
if(h[v] < h[u]) swap(v, u);
for(int i = lg - 1; i >= 0; --i){
if((1 << i) < (h[v] - h[u]) && par[v][i] != -1){
v = par[v][i];
}
}
if(v == u) return v;
for(int i = lg - 1; i >= 0; --i) {
if(par[v][i] != par[u][i] && par[v][i] != -1 && par[u][i] != -1) {
v = par[v][i];
u = par[u][i];
}
}
return par[v][0];
}
bool c(int u, int v) {return h[u] < h[v];}
signed main(){
fast();
cin >> n >> m >> k;
for(int i = 1; i < n; ++i){
int u, v; cin >> u >> v;
u--; v--;
g[u].pb(v);
g[v].pb(u);
mp[mmt(u, v)] = i - 1;
mp[mmt(v, u)] = i - 1;
}
dfs(0);
for(int i = 0; i < m; ++i){
int nn; cin >> nn;
vector<int> x;
for(int j = 0; j < nn; ++j) {int h; cin >> h; x.pb(--h);}
sort(all(x), c);
int lcaa = x[0];
for(int j = 1; j < nn; ++j){
int lc = lca(x[j - 1], x[j]);
cnt[x[j - 1]]++;
cnt[x[j]]++;
cnt[lc] -= 2;
lcaa = lca(lcaa, x[j]);
}
cnt[x[0]]++;
cnt[x.back()]++;
cnt[lcaa] -= 2;
}
dfs2(0);
cout << ans.size() << endl;
for(int u : ans) cout << u + 1 << " ";
}
// The sea will come out of the darkness
// and the people of the sea will return to their homes
// There is no time left. be sure!!
Compilation message
dna.cpp:19: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
19 | #pragma GCC optimization ("O4")
|
dna.cpp:20: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
20 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
101968 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
102132 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
102180 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
104276 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
