| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 197175 | Pankin | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define con continue
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;
using namespace std;
vector< pair<int, int> > dir = {
{
-1, 0
},
{
0, 1
},
{
1, 0
},
{
0, -1
}
};
bool valid(int x, int y, int n, int m) {
return x >= 0 && y >= 0 && x < n && y < m;
}
mt19937 rng(1999999973);
const int N = 2055;
vector<int> g[N];
int n, dp[N][12], h[N], l[N], r[N], orderL[N], orderR[N], o = 0, am;
bool used[N], vis[N];
inline int lca(int u, int v) {
if (u == -1)
return v;
if (v == -1)
return u;
if (h[u] < h[v])
swap(u, v);
for (int j = 11; j >= 0; j--) {
if (h[dp[u][j]] >= h[v])
u = dp[u][j];
}
if (u == v)
return v;
for (int j = 11; j >= 0; j--) {
if (dp[u][j] != dp[v][j]) {
u = dp[u][j]; v = dp[v][j];
}
}
return dp[u][0];
}
map<vector<int>, int> rs;
inline bool good() {
vector<int> mn;
for (int i = 1; i <= n; i++) {
if (used[i])
mn.pb(i);
}
if (mn.size() == n)
return true;
if (mn.empty())
return false;
if (rs.find(mn) != rs.end())
return rs[mn];
am++;
//assert(am <= 100);
return query(mn);
cout << "? " << mn.size() << " ";
for (int i = 0; i < mn.size(); i++)
cout << mn[i] << " ";
cout << endl;
int res;
cin >> res;
if (res == -1) {
exit(0);
}
rs[mn] = res;
return res;
}
void dfs(int v, int p) {
dp[v][0] = p;
l[v] = o;
o++;
for (int j = 1; j < 12; j++) {
dp[v][j] = dp[dp[v][j - 1]][j - 1];
}
for (int i = 0; i < g[v].size(); i++) {
int to = g[v][i];
if (to == p)
continue;
h[to] = h[v] + 1;
dfs(to, v);
}
r[v] = o;
o++;
}
bool compL(int x, int y) {
return l[x] < l[y];
}
bool compR(int x, int y) {
return r[x] < r[y];
}
struct comp {
bool operator()(const int &x, const int &y) const {
return r[x] < r[y];
}
};
inline void del(set<int, comp> &rem, int v) {
rem.erase(v);
}
void goUp(int v, set<int, comp> &rem) {
if (vis[v])
return;
vis[v] = true;
del(rem, v);
goUp(dp[v][0], rem);
}
inline int upper(int v, int d) {
while(d > 0) {
v = dp[v][__builtin_ctz(d)];
d &= d - 1;
}
return v;
}
int findEgg(int cc, vector<pii> bridges) {
n = cc;
for (int i = 1; i <= n; i++) {
used[i] = vis[i] = false;
g[i].clear();
}
for (int i = 0; i < n - 1; i++) {
int u = bridges[i].fs, v = bridges[i].sc;
g[u].pb(v);
g[v].pb(u);
}
for (int i = 1; i <= n; i++) {
orderL[i] = i;
orderR[i] = i;
}
dfs(1, 1);
sort(orderL + 1, orderL + 1 + n, compL);
sort(orderR + 1, orderR + 1 + n, compR);
int firstOut;
int l = 0, r = n - 1;
while(l != r) {
int mid = (l + r + 1) / 2;
for (int i = 1; i <= n; i++)
used[i] = true;
for (int i = 1; i <= mid; i++)
used[orderR[i]] = false;
if (good())
l = mid;
else
r = mid - 1;
}
firstOut = orderR[l + 1];
return firstOut;
}
//signed main() {
// cin >> n;
// for (int i = 0; i < n - 1; i++) {
// int u, v;
// cin >> u >> v;
// g[u].pb(v);
// g[v].pb(u);
// }
// for (int i = 1; i <= n; i++) {
// orderL[i] = i;
// orderR[i] = i;
// }
// dfs(1, 1);
// sort(orderL + 1, orderL + 1 + n, compL);
// sort(orderR + 1, orderR + 1 + n, compR);
//
// while(true) {
// am = 0;
// rs.clear();
// string s;
// cin >> s;
// if (s == "E")
// return 0;
//
// for (int i = 1; i <= n; i++)
// used[i] = vis[i] = false;
// set<int, comp> rem;
// for (int i = 1; i <= n; i++)
// rem.insert(i);
//
// int firstOut, lastIn;
//
// int l = 0, r = n - 1;
// while(l != r) {
// int mid = (l + r + 1) / 2;
// for (int i = 1; i <= n; i++)
// used[i] = true;
// for (int i = 1; i <= mid; i++)
// used[orderR[i]] = false;
//
// if (good())
// l = mid;
// else
// r = mid - 1;
// }
// firstOut = orderR[l + 1];
// for (int i = 1; i <= l; i++)
// del(rem, orderR[i]);
//
// l = 0, r = n - 1;
// while(l != r) {
// int mid = (l + r + 1) / 2;
// for (int i = 1; i <= n; i++)
// used[i] = true;
// for (int i = 1; i <= mid; i++)
// used[orderL[n - i + 1]] = false;
//
// if (good())
// l = mid;
// else
// r = mid - 1;
// }
// lastIn = orderL[n - l];
// for (int i = n; i > n - l; i--) {
// del(rem, orderL[i]);
// }
//
// int root = lca(firstOut, lastIn);
// vis[root] = true;
// del(rem, root);
//
// int curCol = 2;
//
// goUp(firstOut, rem);
// goUp(lastIn, rem);
//
// for (int i = 1; i <= n; i++)
// if (lca(i, root) != root)
// del(rem, i);
//
// for (int i = 1; i <= n; i++) {
// used[i] = (lca(i, root) == root);
// }
// if (root != 1 && !good()) {
// int lastOut;
// l = 0, r = h[root];
//
// while(l != r) {
// int mid = (l + r) / 2;
// int anc = upper(root, mid);
// for (int i = 1; i <= n; i++) {
// used[i] = (lca(i, anc) == anc);
// }
//
// if (good())
// r = mid;
// else
// l = mid + 1;
// }
//
// lastOut = upper(root, l);
// del(rem, lastOut);
// vis[lastOut] = true;
//
// goUp(dp[root][0], rem);
// curCol++;
// }
//
// while(rem.size() > 0 && curCol < 10) {
// l = 0, r = rem.size();
// while(l != r) {
// int mid = (l + r + 1) / 2;
// for (int i = 1; i <= n; i++) {
// used[i] = vis[i];
// }
// for (auto i = rem.begin(); i != rem.end(); i++) {
// used[*i] = true;
// }
// auto it = rem.begin();
// for (int i = 1; i <= mid; i++, it++)
// used[*it] = false;
//
// if (good())
// l = mid;
// else
// r = mid - 1;
// }
// if (l == rem.size()) {
// break;
// }
// int cr = 0;
// while(cr != l) {
// rem.erase(rem.begin());
// cr++;
// }
// goUp(*rem.begin(), rem);
// curCol++;
// }
//
// vector<int> ans;
// for (int i = 1; i <= n; i++) {
// if (vis[i]) {
// int col = 0;
// for (int j = 0; j < g[i].size(); j++)
// col += vis[g[i][j]];
// if (col <= 1)
// ans.pb(i);
// }
// }
//
// cout << "! " << ans.size() << " ";
// for (int i = 0; i < ans.size(); i++)
// cout << ans[i] << " ";
// cout << endl;
//
// }
//
// return 0;
//}
//
///*
//6
//1 2
//2 3
//3 4
//3 5
//3 6
//S
//*/