| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 237527 | IgorI | Friends (BOI17_friends) | C++17 | 6 ms | 1536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL
vector<vector<int> > ans;
int n, p, q;
vector<int> g[5000];
int a[50000];
int b[50000];
vector<int> graph[5000];
int c[3000][3000];
int color[3000];
int in[3000];
int up[3000];
int T = 1;
int marker;
int sz[3000];
int ok[3000];
int success;
bool no(vector<int> &v, int x)
{
forn(i, v.size()) if (v[i] == x) return 0;
return 1;
}
int dfs(int v, int par, int End, int Start)
{
if (!success) return 0;
sz[v] = 1;
in[v] = up[v] = T++;
for (auto e : graph[v])
{
int u = a[e] + b[e] - v;
if (u == par) continue;
if (v == End && u == Start) continue;
if (v == Start && u == End) continue;
if (in[u] == 0)
{
dfs(u, v, End, Start);
sz[v] += sz[u];
}
up[v] = min(up[v], up[u]);
}
cout << v << " " << sz[v] << " " << in[v] << " " << up[v] << endl;
if (up[v] == in[v])
{
//this node is top
vector<int> q = {v};
vector<int> down_sizes;
for (int i = 0; i < q.size(); i++)
{
for (auto id : graph[q[i]])
{
int u = a[id] + b[id] - q[i];
if (up[u] < up[v]) continue;
int t = 0;
for (int j = 0; j < q.size(); j++) if (q[j] == u) t = 1;
if (t == 1) continue;
if (ok[u])
{
down_sizes.push_back(sz[u]);
}
else
{
q.push_back(u);
}
}
if (q.size() > 15)
{
success = 0;
return 0;
}
}
if (down_sizes.size() == 0)
{
int fl = 0;
for (int i = 0; i < q.size(); i++) if (q[i] == End) fl = 1;
cout << q.size() << " " << p << " " << fl << endl;
if (q.size() <= p && fl)
{
ok[v] = 1;
return 1;
}
else
{
if (q.size() >= p)
{
success = 0;
return 0;
}
else
{
return 1;
}
}
}
if (down_sizes.size() == 1)
{
int our = sz[v] - down_sizes[0];
if (our <= p)
{
ok[v] = 1;
return 1;
}
else
{
success = 0;
return 0;
}
}
exit(1);
}
return success;
}
void opa(int v)
{
marker++;
vector<int> q = {v};
color[v] = marker;
vector<int> ids;
for (int i = 0; i < q.size(); i++)
{
for (int j = 0; j < graph[q[i]].size(); j++)
{
int u = a[graph[q[i]][j]] + b[graph[q[i]][j]] - q[i];
if (color[u] == 0)
{
color[u] = marker;
ids.push_back(graph[q[i]][j]);
q.push_back(u);
}
}
}
if (q.size() <= p)
{
ans.push_back(q);
return;
}
for (int i = 0; i < q.size(); i++)
{
for (int j = 0; j < q.size(); j++)
{
if (i != j)
{
success = 1;
T = 1;
fill(in, in + 2000, 0);
fill(up, up + 2000, 0);
cout << q[i] << " " << q[j] << endl;
if (dfs(q[i], q[i], q[j], q[i]))
{
return;
}
}
}
}
cout << "detention";
exit(0);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> p >> q;
for (int i = 0; i < n; i++)
{
int k;
cin >> k;
g[i].resize(k);
for (int j = 0; j < k; j++)
{
cin >> g[i][j];
c[i][g[i][j]] = 1;
}
}
int f = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (c[i][j] + c[j][i] == 1)
{
cout << "detention";
return 0;
}
if (c[i][j])
{
graph[i].push_back(f);
graph[j].push_back(f);
a[f] = i;
b[f] = j;
f++;
}
}
}
if (q == 0)
{
//each component size <= p
vector<vector<int> > ans;
for (int i = 0; i < n; i++)
{
if (color[i] == 0)
{
vector<int> s = {i};
color[i] = 1;
for (int j = 0; j < s.size(); j++)
{
for (auto id : graph[s[j]])
{
int u = a[id] + b[id] - s[j];
if (color[u] == 0)
{
color[u] = 1;
s.push_back(u);
}
}
}
if (s.size() > p)
{
cout << "detention";
return 0;
}
ans.push_back(s);
}
}
cout << "home\n";
forn(i, ans.size())
{
cout << ans[i].size() << " ";
forn(j, ans[i].size())
{
cout << ans[i][j] << " ";
}
cout << "\n";
}
return 0;
}
if (q == 1)
{
//each component can be splitted in two with sizes <= p
vector<vector<int> > ans;
for (int i = 0; i < n; i++)
{
if (color[i] == 0)
{
vector<int> s = {i};
color[i] = 1;
vector<int> ids;
for (int j = 0; j < s.size(); j++)
{
for (auto id : graph[s[j]])
{
int u = a[id] + b[id] - s[j];
if (color[u] == 0)
{
color[u] = 1;
s.push_back(u);
ids.push_back(id);
}
}
}
if (s.size() > 2 * p)
{
cout << "detention";
return 0;
}
if (s.size() <= p)
{
ans.push_back(s);
continue;
}
int fl = 0;
for (auto e : ids)
{
int v1 = a[e], v2 = b[e];
vector<int> r = {v2, v1}, s = {v1, v2};
for (int i = 1; i < r.size(); i++)
{
for (auto id : graph[r[i]])
{
int u = a[id] + b[id] - r[i];
if (no(r, u))
{
r.push_back(u);
}
}
}
for (int i = 1; i < s.size(); i++)
{
for (auto id : graph[s[i]])
{
int u = a[id] + b[id] - s[i];
if (no(s, u))
{
s.push_back(u);
}
}
}
reverse(all(r));
reverse(all(s));
r.pop_back();
s.pop_back();
if (r.size() <= p && s.size() <= p)
{
ans.push_back(r);
ans.push_back(s);
fl = 1;
break;
}
}
if (!fl)
{
cout << "detention\n";
return 0;
}
}
}
cout << "home\n";
cout << ans.size() << "\n";
forn(i, ans.size())
{
cout << ans[i].size() << " ";
forn(j, ans[i].size())
{
cout << ans[i][j] << " ";
}
cout << "\n";
}
return 0;
}
for (int i = 0; i < n; i++)
{
if (color[i] == 0)
{
opa(i);
}
}
cout << "home\n";
cout << ans.size() << "\n";
forn(i, ans.size())
{
cout << ans[i].size() << " ";
forn(j, ans[i].size())
{
cout << ans[i][j] << " ";
}
cout << "\n";
}
}
/* Note:
Check constants at the beginning of the code.
N is set to 4e5 but be careful in problems with large constant factor.
Setting N in every problem is more effective.
Check corner cases.
N = 1
No def int long long for now.
Add something here.
*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||