| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 965404 | Trisanu_Das | Bitaro’s Party (JOI18_bitaro) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
const int B = 150;
int n, m, q;
typedef pair<int, int> pi;
vector<int> prv[maxn], vis(maxn, -1), val(maxn), y(maxn, -1);
vector<pi> far[maxn];
bool cmp(int x, int y){
return val[x] > val[y];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 0; i < m; i ++){
int x, y;
cin >> x >> y;
x --; y --;
prv[y].push_back(x);
}
for (int i = 0; i < n; i ++){
vector<int> all;
for (int j = 0; j < (int)prv[i].size(); j ++){
int x = prv[i][j];
for (int k = 0; k < far[x].size(); k ++){
int z = far[x][k].second;
if (vis[z] != i){
vis[z] = i;
all.push_back(z);
val[z] = far[x][k].first + 1;
} else val[z] = max(val[z], far[x][k].first + 1);
}
if (vis[x] != i){
vis[x] = i;
all.push_back(x);
val[x] = 1;
}
}
all.push_back(i);
sort(all.begin(), all.end(), cmp);
for (int j = 0; j < min((int)all.size(), B); j ++)
far[i].push_back(make_pair(val[all[j]], all[j]));
}
while(q --){
int t; cin >> t; t --;
int r; cin >> r;
for (int i = 0; i < r; i ++){
int p; cin >> p; y[p - 1] = q;
}
if (r >= B){
vector<int> dp(n, -1);
for (int i = 0; i <= t; i ++){
if (y[i] != q) p[i] = max(dp[i], 0);
for (int j = 0; j < (int)prv[i].size(); j ++)
if (dp[prv[i][j]] != -1)
dp[i] = max(dp[i], dp[prv[i][j]] + 1);
}
cout << dp[t] << '\n';
} else{
for (int i = 0; i < (int)far[t].size(); i ++){
if (y[far[t][i].second] != q){
cout << far[t][i].first << '\n';
goto done;
}
}
cout << -1 << '\n';
done: continue;
}
}
}