| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 779267 | anhphant | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 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.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void pre_setting() {
srand(time(NULL));
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("birato.inp")) {
freopen("birato.inp", "r", stdin);
freopen("birato.out", "w", stdout);
}
#endif // ONLINE_JUDGE
}
namespace subtask2 {
int N, M, Q, is_visited[100007], longest_path[100007], T, Y, C[100007];
vector<int> GR[100007], invGR[100007];
vector<int> topo_order;
void init() {
cin >> N >> M >> Q;
for(int i = 1, s, e; i <= M; i++) {
cin >> s >> e;
GR[s].push_back(e);
invGR[e].push_back(s);
}
}
void topo_dfs(int u) {
is_visited[u] = 1;
for(int v : GR[u]) {
if (!is_visited[v]) topo_dfs(v);
}
topo_order.push_back(u);
}
void topo_find() {
for(int i = 1; i <= N; i++)
if (!is_visited[i]) topo_dfs(i);
reverse(topo_order.begin(), topo_order.end());
//for(int u : topo_order) cerr << u << " "; cerr << endl;
}
void solve() {
init();
topo_find();
while(Q--) {
//cerr << "START CASE : " << endl;
cin >> T >> Y;
for(int i = 1; i <= Y; i++) cin >> C[i];
for(int i = 0; i <= N; i++) longest_path[i] = -1e9;
longest_path[T] = 0;
for(int i = N - 1; i >= 0; i--) {
int u = topo_order[i];
if (longest_path[u] == -1e9) continue;
for(int v : invGR[u]) {
longest_path[v] = max(longest_path[v], longest_path[u] + 1);
}
}
sort(C + 1, C + 1 + Y);
int ans = -1, idxC = 1;
for(int i = 1; i <= N; i++) {
if (idxC <= Y && C[idxC] == i) {
idxC++;
}
else {
ans = max(ans, longest_path[i]);
//cerr << i << " " << longest_path[i] << endl;
}
}
cout << ans << endl;
}
}
}
namespace subtask3 {
int N, M, Q, is_visited[100007], longest_path[100007], T, Y, C[100007];
vector<int> GR[100007], invGR[100007];
vector<int> topo_order;
vector<pair<int, int>> vlist[100007];
const int B = 3;
void init() {
cin >> N >> M >> Q;
for(int i = 1, s, e; i <= M; i++) {
cin >> s >> e;
GR[s].push_back(e);
invGR[e].push_back(s);
}
}
bool added[100007];
void vlist_construct() {
for(int i = 1; i <= N; i++) vlist[i].push_back({i, 0});
for(int u = 1; u <= N; u++) {
//cerr << u << endl;
for(int v : GR[u]) {
vector<pair<int, int>> tmp;
int pl = 0, pr = 0;
while(pl < vlist[u].size() || pr < vlist[v].size()) {
//cerr << pl << " " << pr << endl;
if (pl < vlist[u].size() && vlist[u][pl].second + 1 > vlist[v][pr].second) {
if (!added[vlist[u][pl].first])
tmp.push_back({vlist[u][pl].first, vlist[u][pl].second + 1});
added[vlist[u][pl].first] = 1;
pl++;
}
else {
if (!added[vlist[v][pr].first])
tmp.push_back(vlist[v][pr]);
added[vlist[v][pr].first] = 1;
pr++;
}
if (tmp.size() - 2 == B) break;
}
vlist[v] = tmp;
for(auto [zzz, k] : vlist[v]) added[zzz] = 0;
}
}
}
void solve() {
init();
vlist_construct();
for(int i = 1; i <= N; i++) {
sort(vlist[i].begin(), vlist[i].end(), [] (pair<int, int>& x1, pair<int, int>& x2) {
return x1.second > x2.second;
});
//cerr << "i = " << i << endl;
//for(auto [tt, v] : vlist[i]) cerr << tt << " : " << v << endl;
//cerr << endl;
}
fill(is_visited + 1, is_visited + 1 + N, 1);
while(Q--) {
//cerr << "START CASE" << endl;
cin >> T >> Y;
for(int i = 1; i <= Y; i++) {
cin >> C[i];
is_visited[C[i]] = 0;
}
//cerr << T << endl;
sort(C + 1, C + 1 + Y);
if (Y >= B) {
//cerr << "case 1" << endl;
for(int i = 1; i <= T; i++) longest_path[i] = -1e9;
for(int i = 1; i <= T; i++) {
//cerr << "init : " << i << " " << longest_path[i] << endl;
if (is_visited[i]) longest_path[i] = max(longest_path[i], 0);
if (longest_path[i] == -1e9) continue;
//cerr << i << " " << longest_path[i] << endl;
for(int v : GR[i]) {
longest_path[v] = max(longest_path[v], longest_path[i] + 1);
//cerr << "v : " << v << " " << longest_path[v] << endl;
}
}
cout << (longest_path[T] < 0? -1 : longest_path[T]) << endl;
}
else {
//cerr << "case 2" << endl;
for(auto [u, d] : vlist[T]) {
//cerr << u << " " << d << endl;
if (is_visited[u]) {
cout << d << endl;
goto GT;
}
}
cout << -1 << endl;
GT:
int hope = -1;
}
for(int i = 1; i <= Y; i++) is_visited[C[i]] = 1;
}
}
}
int main() {
pre_setting();
subtask3 :: solve();
}