QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#322403 | #121. Bitaro's Party | NintsiChkhaidze | 0 | 2ms | 5616kb | C++20 | 2.3kb | 2024-02-06 23:40:46 | 2024-02-06 23:40:47 |
answer
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,
using namespace std;
const int N = 2e5 + 3;
int b[N],id,vis[N],fix[N],dp[N],f[N];
vector <int> g[N],v[N],ord;
vector <pii> paths[N];
void topsort(int x){
vis[x]=1;
for (int to: v[x])
if (!vis[to]) topsort(to);
ord.pb(x);
}
vector <pii> merge(vector <pii> x,vector <pii> y){
for (int i = 0; i < x.size(); i++)
x[i].f += 1;
++id;
int l1 = 0,l2 = 0;
vector <pii> vec;
while (l1 < x.size() || l2 < y.size()){
while (l1 < x.size() && fix[x[l1].s] == id) l1++;
while (l2 < y.size() && fix[y[l2].s] == id) l2++;
if (l1 == x.size()) {
vec.pb(y[l2]);
fix[y[l2].s] = id;
++l2;
continue;
}
if (l2 == y.size()){
vec.pb(x[l1]);
fix[x[l1].s] = id;
++l1;
continue;
}
if (x[l1] > y[l2]) {
vec.pb(x[l1]);
fix[x[l1].s] = id;
++l1;
continue;
}
vec.pb(y[l2]);
fix[y[l2].s] = id;
++l2;
}
return vec;
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n,m,q;
cin>>n>>m>>q;
for (int i = 1; i <= m; i++){
int a,b;
cin>>a>>b;
g[b].pb(a);
v[a].pb(b);
}
for (int i = 1; i <= n; i++){
if (!vis[i]) topsort(i);
}
reverse(ord.begin(),ord.end());
int Bl = 320;
for (int x: ord){
vector <pii> cur;
cur.pb({0,x});
for (int prev: g[x]){
cur = merge(paths[prev], cur);
}
for (int i = 0; i < cur.size(); i++){
if (paths[x].size() == Bl) break;
paths[x].pb(cur[i]);
}
}
while (q--){
int T,k;
cin>>T>>k;
for (int i = 1; i <= k; i++){
int x;
cin>>x;
b[i] = x;
f[x] = 1;
}
int ans=0;
if (k < Bl){
for (auto [l,r]: paths[T]){
if (!f[r]) {ans = l; break;}
}
cout<<ans<<endl;
}else{
for (int i = 1; i <= n; i++){
if (f[i]) dp[i] = -1e9;
else dp[i] = 0;
}
for (int x: ord){
for (int prev: g[x]){
dp[x] = max(dp[x],dp[prev] + 1);
}
}
if (dp[T] < 0) cout<<-1<<endl;
else cout<<dp[T]<<endl;
}
for (int i = 1; i <= k; i++)
f[b[i]] = 0;
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 1ms
memory: 3504kb
input:
1 0 1 1 0
output:
0
result:
ok single line: '0'
Test #2:
score: -7
Wrong Answer
time: 2ms
memory: 5616kb
input:
1 0 1 1 1 1
output:
0
result:
wrong answer 1st lines differ - expected: '-1', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%