Submission #3607936
Source Code Expand
#include<map> #include<bitset> #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<set> #include<string> #include<chrono> #include<stack> #include<fstream> #define REP(i,x,y) for(ll i=x;i<=y;i++) #define SIZE(a) ll(a.size()) #define vll vector<ll> #define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m #define BIT(n) (ll(1)<<n) #define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) #define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1 #define SORT(a,n) sort(a+1,a+n+1) #define SORT_O(a,n,order) sort(a+1,a+n+1,order) #define PER(i,y,x) for(ll i=y;i>=x;i--) typedef long long ll; using namespace std; /* struct point { long long dist; long long name; bool operator<(const point& rhs) const { return dist > rhs.dist; } }; */ ll const MAX = 500005; vll edge[MAX]; ll parent[MAX]; ll n; ll tour[MAX]; ll root; ll color[MAX] = {}; ll rk[MAX]; ll tour_ord[MAX]; bool ord(ll x, ll y) { return tour_ord[x] < tour_ord[y]; } void dfs() { stack<ll> st; st.push(1); rk[root] = 0; parent[1] = 1; ll cnt = 1; while (!st.empty()) { ll cur = st.top(); if (color[cur] == 0) { color[cur] = 1; tour[cnt] = cur; cnt++; REP(i, 0, edge[cur].size() - 1) { ll next = edge[cur][i]; if (color[next] == 0) { st.push(next); rk[next] = rk[cur] + 1; parent[next] = cur; } } } else { st.pop(); color[cur] = 2; } } REP(i, 1, n) { tour_ord[tour[i]] = i; } } ll parents[MAX][105]; void init() { REP(i, 1, n) { parents[i][0] = parent[i]; } REP(i, 1, 50) { REP(j, 1, n) { parents[j][i] = parents[parents[j][i - 1]][i - 1]; } } } ll getanc(ll x, ll t) { ll bit = 0; while (t > 0) { if ((t&BIT(bit))>0) { t ^= BIT(bit); x = parents[x][bit]; } bit++; } return x; } ll lca(ll x, ll y) { if (x == y) return x; if (rk[x] < rk[y]) swap(x, y); ll t = rk[x] - rk[y]; x = getanc(x, t); if (x == y) return x; ll bit = 0; while (BIT(bit) <= rk[x]) { bit++; } while (bit >= 0) { if (parents[x][bit] != parents[y][bit]) { x = parents[x][bit]; y = parents[y][bit]; } bit--; } return parent[x]; } int main() { cin >> n; REP(i, 1, n - 1) { ll a, b; cin >> a >> b; edge[a].push_back(b); edge[b].push_back(a); } root = 1; dfs(); init(); //REP(i, 1, n) cout << tour[i] << " "; //cout << endl; ll qqq; cin >> qqq; REP(iii, 1, qqq) { ll m, k; cin >> m >> k; ll ans = -1e9; vll v; REP(i, 1, m) { ll t; cin >> t; v.push_back(t); } sort(v.begin(), v.end(), ord); for (ll i = 0; i + k - 1 < v.size(); i++) { ll j = i + k - 1; //cout << i << " " << j << endl; //cout << v[i] << " " << v[j] << " " << endl; ll u = lca(v[i], v[j]); //cout << "!" << u << endl; ans = max(ans, rk[u]); } cout << ans << endl; } }
Submission Info
Submission Time | |
---|---|
Task | F - 根付き木のみさわさん |
User | nejineji |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2967 Byte |
Status | RE |
Exec Time | 416 ms |
Memory | 115452 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 20 | 0 / 110 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt |
Subtask2 | sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_15.txt, subtask_02_16.txt, subtask_02_17.txt, subtask_02_18.txt, subtask_02_19.txt, subtask_02_20.txt, subtask_02_21.txt, subtask_02_22.txt, subtask_02_23.txt, subtask_02_24.txt, subtask_02_25.txt, subtask_02_26.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 8 ms | 23936 KB |
sample_02.txt | AC | 8 ms | 23936 KB |
sample_03.txt | AC | 8 ms | 23936 KB |
subtask_01_01.txt | RE | 106 ms | 21888 KB |
subtask_01_02.txt | AC | 8 ms | 23936 KB |
subtask_01_03.txt | AC | 8 ms | 23936 KB |
subtask_01_04.txt | AC | 9 ms | 23936 KB |
subtask_01_05.txt | AC | 38 ms | 23936 KB |
subtask_01_06.txt | AC | 8 ms | 23936 KB |
subtask_01_07.txt | AC | 9 ms | 23936 KB |
subtask_01_08.txt | AC | 36 ms | 23936 KB |
subtask_01_09.txt | AC | 8 ms | 23936 KB |
subtask_01_10.txt | AC | 9 ms | 23936 KB |
subtask_01_11.txt | AC | 36 ms | 23936 KB |
subtask_01_12.txt | AC | 8 ms | 23936 KB |
subtask_01_13.txt | AC | 9 ms | 23936 KB |
subtask_01_14.txt | AC | 36 ms | 23936 KB |
subtask_01_15.txt | AC | 8 ms | 23936 KB |
subtask_01_16.txt | AC | 9 ms | 23936 KB |
subtask_01_17.txt | AC | 37 ms | 23936 KB |
subtask_01_18.txt | AC | 8 ms | 23936 KB |
subtask_01_19.txt | AC | 9 ms | 23936 KB |
subtask_01_20.txt | AC | 36 ms | 24064 KB |
subtask_01_21.txt | AC | 8 ms | 23936 KB |
subtask_01_22.txt | AC | 9 ms | 23936 KB |
subtask_01_23.txt | AC | 36 ms | 23936 KB |
subtask_01_24.txt | AC | 8 ms | 23936 KB |
subtask_01_25.txt | AC | 9 ms | 23936 KB |
subtask_01_26.txt | AC | 36 ms | 23936 KB |
subtask_02_01.txt | AC | 204 ms | 115320 KB |
subtask_02_02.txt | AC | 208 ms | 114560 KB |
subtask_02_03.txt | AC | 223 ms | 114432 KB |
subtask_02_04.txt | AC | 210 ms | 115452 KB |
subtask_02_05.txt | AC | 202 ms | 114488 KB |
subtask_02_06.txt | AC | 222 ms | 114432 KB |
subtask_02_07.txt | AC | 235 ms | 114220 KB |
subtask_02_08.txt | AC | 236 ms | 113612 KB |
subtask_02_09.txt | AC | 253 ms | 113256 KB |
subtask_02_10.txt | AC | 203 ms | 114168 KB |
subtask_02_11.txt | AC | 233 ms | 113212 KB |
subtask_02_12.txt | AC | 250 ms | 113280 KB |
subtask_02_13.txt | AC | 217 ms | 114812 KB |
subtask_02_14.txt | AC | 315 ms | 114300 KB |
subtask_02_15.txt | AC | 236 ms | 113984 KB |
subtask_02_16.txt | AC | 222 ms | 114116 KB |
subtask_02_17.txt | AC | 226 ms | 113396 KB |
subtask_02_18.txt | AC | 245 ms | 113228 KB |
subtask_02_19.txt | AC | 214 ms | 114812 KB |
subtask_02_20.txt | AC | 227 ms | 114008 KB |
subtask_02_21.txt | AC | 250 ms | 113792 KB |
subtask_02_22.txt | AC | 239 ms | 114152 KB |
subtask_02_23.txt | AC | 234 ms | 113684 KB |
subtask_02_24.txt | AC | 270 ms | 113204 KB |
subtask_02_25.txt | AC | 412 ms | 113920 KB |
subtask_02_26.txt | AC | 416 ms | 113740 KB |