이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define pb push_back
#define se second
const int N = 1e5+5;
const int INF = 1e9;
int SIZE;
int n, m, q;
bool allow[N], used[N];
int block[N];
vector<ii> best[N];
vector<int> graph[N], adj[N];
void prep() {
for(int i=1;i<=n;i++){
for(int x:graph[i]){
vector<ii>fin;
best[x].push_back({0,x});
//duplicates are dangerous
//remove duplicates while doing merge sort
int a = 0,b=0;
int sa = sz(best[x]);
int sb = sz(best[i]);
while(sz(fin)<SIZE && (a<sa || b < sb)){
if(b == sb || (a!=sa && best[x][a].fi+1 >= best[i][b].fi)){
best[x][a].fi++;
fin.pb(best[x][a]);
used[best[x][a].se] = 1;
best[x][a].fi--;
a++;
}else{
fin.pb(best[i][b]);
used[best[i][b].se] = 1;
b++;
}
while(a<sa && used[best[x][a].se])a++;
while(b<sb && used[best[i][b].se])b++;
}
best[x].pop_back();
for(auto z:fin) used[z.se] = 0;
swap(best[i],fin);
}
}
}
int dp[N];
void solve() {
cin >> n >> m >> q;
SIZE = 350;
for(int i=0; i<m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
graph[v].push_back(u);
}
fill(allow, allow+n+1, 1);
prep();
for(int t=0; t<q; ++t) {
int s, c;
cin >> s >> c;
for(int j=0; j<c; ++j) {
cin >> block[j];
allow[block[j]] = 0;
}
int ans = -1;
if (s < SIZE) {
bool found = 0;
for(auto cand : best[s]) if (allow[cand.se]) {
ans = cand.fi;
found = 1;
break;
}
if (allow[s]) ans = max(ans, 0);
}
else {
for(int i=1; i<=n; ++i)
dp[i] = -1;
dp[s] = 0;
if (allow[s]) ans = 0;
for(int i=s-1; i>0; --i) {
for(int x : adj[i]) if (dp[x] != -1)
dp[i] = max(dp[i], dp[x] + 1);
if (allow[i]) ans = max(ans, dp[i]);
}
}
cout << ans << "\n";
for(int j=0; j<c; ++j) {
allow[block[j]] = 1;
}
}
// for(int i=1; i<=n; ++i) {
// cout << "From " << i << " Has " << best[i].size() << " Choices: \n";
// for(auto v : best[i]) cout << "Vertice " << v.fi << " Dist " << v.se << "\n";
// cout << "------------\n";
// }
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("input.inp", "r")) {
freopen("input.inp", "r", stdin);
freopen("input.out", "w", stdout);
}
solve();
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'void solve()':
bitaro.cpp:85:12: warning: variable 'found' set but not used [-Wunused-but-set-variable]
85 | bool found = 0;
| ^~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen("input.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen("input.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |