| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 238318 | Charis02 | Bitaro’s Party (JOI18_bitaro) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<unordered_set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7
using namespace std;
ll n,m,q;
vector < pi > longest[N];
bool used[N];
vector < int > graph[N];
unordered_set < int > busy;
ll root;
int time;
int last[N],dp[N];
void merge_lists(vector < pi > &result,const vector < pi > &add)
{
vector < pi > r;
r.clear();
int p1 = 0;
int p2 = 0;
while((p1 < result.size() || p2 < add.size()) && r.size() < root)
{
if(p1 == result.size())
{
if(!used[add[p2].second])
r.push_back(mp(add[p2].first+1,add[p2].second));
used[add[p2].second] = true;
p2++;
}
else if(p2 == add.size())
{
if(!used[result[p1].second])
r.push_back(result[p1]);
used[result[p1].second] = true;
p1++;
}
else if(result[p1].first < add[p2].first+1)
{
if(!used[add[p2].second])
r.push_back(mp(add[p2].first+1,add[p2].second));
used[add[p2].second]=true;
p2++;
}
else
{
if(!used[result[p1].second])
r.push_back(result[p1]);
used[result[p1].second]=true;
p1++;
}
}
result = r;
rep(i,0,result.size())
used[result[i].second]=false;
return;
}
void precalc()
{
rep(i,1,n+1)
longest[i].push_back(mp(0,i));
rep(i,1,n+1)
{
rep(j,0,graph[i].size())
{
int v = graph[i][j];
merge_lists(longest[v],longest[i]);
}
}
return;
}
int solve_smart(int target)
{
dp[target]=-1;
if(busy.count(target)==0)
dp[target] = 0;
rep(i,1,target)
{
if(busy.count(i)!=0)
continue;
if(last[i] != time)
dp[i] = 0;
last[i] = time;
rep(j,0,graph[i].size())
{
int v = graph[i][j];
if(last[v] != time)
dp[v] = -1;
dp[v]=max(dp[i]+1,dp[v]);
last[v]=time;
}
}
return dp[target];
}
int solve_simple(int target)
{
rep(i,0,longest[target].size())
{
if(busy.count(longest[target][i].second) == 0)
return longest[target][i].first;
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
root = sqrt(n);
rep(i,0,m)
{
int a,b;
cin >> a >> b;
graph[a].push_back(b);
}
precalc();
rep(i,0,q)
{
time=i+1;
int t,y,a;
busy.clear();
cin >> t >> y;
rep(j,0,y)
{
cin >> a;
busy.insert(a);
}
if(y < root)
cout << solve_smart(t) << "\n";
else
cout << solve_simple(t) << "\n";
}
return 0;
}