이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 7;
const ll oo = 1e15 + 69;
const int sz = 320;
int n, m, q, u, v, t, y, c, id[maxn], d[maxn];
bool vis[maxn];
vector<int> g[maxn], topo, arc[maxn];
struct val {
int f, s;
friend bool operator < (const val a, const val b){
return (a.f > b.f | (a.f == b.f && a.s > b.s));
}
};
bool cmp(const val a, const val b) {
return a.f < b.f;
}
multiset<pa> f[maxn];
void dfs(int u) {
vis[u] = 1;
for(auto v:g[u])
if(!vis[v]) dfs(v);
topo.pb(u);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>n>>m>>q;
while(m--) {
cin>>u>>v;
g[u].pb(v);
arc[v].pb(u);
}
for(int i = 1; i <= n; i++)
if(!vis[i]) dfs(i);
reverse(all(topo));
for(int i = 1; i <= n; i++) f[i].insert({0, i});
for(auto u:topo) {
for(auto k:f[u]) {
if(k.se == -1) continue;
for(auto v:g[u]) {
if(f[v].size() == sz) f[v].erase(f[v].find(*f[v].begin()));
f[v].insert({k.fi + 1, k.se});
}
}
}
for(int k = 1; k <= q; k++) {
cin>>t>>y;
for(int i = 0; i < y; i++) {
cin>>c;
id[c] = k;
}
if(y >= sz) {
fill_n(d, n + 1, -1);
d[t] = 0;
int ans = -1;
if(id[t] != k) ans = 0;
bool ok = 0;
for(int i = topo.size() - 1; i >= 0; i--) {
int u = topo[i];
if(d[u] == -1 || (u != t && !ok)) continue;
if(u > t) continue;
if(u == t) ok = 1;
for(auto v:arc[u]) {
maxi(d[v], d[u] + 1);
if(v <= t && id[v] != k) maxi(ans, d[v]);
}
}
cout<<ans<<"\n";
} else {
int ans = -1;
for(auto i:f[t]) {
int u = i.se;
if(u == -1 || id[u] == k || u > t) continue;
maxi(ans, i.fi);
}
cout<<ans<<"\n";
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'bool operator<(val, val)':
bitaro.cpp:29:21: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
29 | return (a.f > b.f | (a.f == b.f && a.s > b.s));
| ~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |