이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define ii pair<int,int>
#define FOR(i,a,b) for(int i = a ; i < b ; ++i)
const int N = 1e5 + 1;
const int B = 250;
vector<int> g[N];
vector<ii> opt[N];
void pus(int u,int v) {
int a = 0;
int b = 0;
for(ii &e : opt[v]) e.X++;
vector<ii> clone;
while (a < opt[u].size() && b < opt[v].size()) {
if (opt[u][a] < opt[v][b])
clone.pb(opt[v][b++]);
else
clone.pb(opt[u][a++]);
}
while (a < opt[u].size()) clone.pb(opt[u][a++]);
while (b < opt[v].size()) clone.pb(opt[v][b++]);
while (clone.size() > B) clone.pop_back();
for(ii &e : opt[v]) e.X--;
opt[u].swap(clone);
}
int vis[N];
int ban[N];
int len[N];
int tot = 1;
int dfs(int u) {
if (vis[u]) return 0;
vis[u] = 1;
opt[u].pb(ii(0,u));
for(int v : g[u]) {
dfs(v);
pus(u,v);
}
sort (opt[u].begin(),opt[u].end(),greater<ii>());
for(; opt[u].size() > B ; opt[u].pop_back());
return 1;
}
int cal(int u) {
if (vis[u]) return len[u];
len[u] = (ban[u] ? -N : 0);
vis[u] = 1;
for(int v : g[u])
len[u] = max(len[u],cal(v) + 1);
return len[u];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
int m; cin >> m;
int q; cin >> q;
FOR(i,0,m) {
int x; cin >> x;
int y; cin >> y;
g[y].pb(x);
}
FOR(i,1,n + 1) if(!vis[i]) dfs(i);
FOR(i,1,q + 1) {
int u; cin >> u;
int k; cin >> k;
vector<int> vv;
FOR(i,0,k) {
int x; cin >> x;
ban[x] = 1;
vv.pb(x);
}
int ans = -1;
if (k < B) {
for(ii e : opt[u])
if(!ban[e.Y])
ans = max(ans,e.X);
}
else {
fill(vis + 1,vis + 1 + n,0);
ans = max(ans,cal(u));
}
for(int x : vv)
ban[x] = 0;
cout << ans << "\n";
}
}
/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
*/
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'void pus(int, int)':
bitaro.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (a < opt[u].size() && b < opt[v].size()) {
~~^~~~~~~~~~~~~~~
bitaro.cpp:26:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (a < opt[u].size() && b < opt[v].size()) {
~~^~~~~~~~~~~~~~~
bitaro.cpp:32:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (a < opt[u].size()) clone.pb(opt[u][a++]);
~~^~~~~~~~~~~~~~~
bitaro.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (b < opt[v].size()) clone.pb(opt[v][b++]);
~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |