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 <bits/stdc++.h>
using namespace std;
// Miscellanous
#define gc getchar_unlocked
#define ll long long
#define ull unsigned long long
#define si(x) scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define sstr(s) cin >> s
#define pi(x) printf("%d\n",x)
#define pi2(x,y) printf("%d %d\n",x,y)
#define pl(x) printf("%lld\n",x)
#define pl2(x,y) printf("%lld %lld\n",x,y)
#define ps(s) cout << s << endl
#define py printf("YES\n")
#define pn printf("NO\n")
#define pnl printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define revsort(v) sort(v.rbegin(),v.rend())
#define reverse(v) reverse(all(v))
#define alla(arr,sz) arr,arr+sz
#define sorta(arr,sz) sort(alla(arr,sz))
#define reversea(arr,sz) reverse(alla(arr,sz))
#define cta(x,v) count(alla(arr,sz),x)
#define ct(x,v) count(all(v),x)
#define cto(v) count_if(all(v),[] (int a) {return a%2 == 1;})
#define cte(v) count_if(all(v),[] (int a) {return a%2 == 0;})
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define clr(x) memset(x, 0, sizeof(x))
// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define forr(i,s,e) for (int (i)=(s);(i)>=(e);--(i))
#define foreach(val,cont) for (auto &(val) : (cont))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)
// Constants
#define PI 3.1415926535897932384626
#define sqr(x) ((x) * 1ll * (x))
const int mod = 1000000007;
// Containers
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<string,string> pss;
typedef map<int, int> mii;
// Input Output
#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a) vi a(n); rep(i,n) si(a[i])
#define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i])
#define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i])
// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
inline string inttostr(ll a){
char x[100];
sprintf(x,"%lld",a); string s = x;
return s;
}
inline ll strtoint(string a){
char x[100]; ll res;
strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
return res;
}
inline string getstr(void){
char x[1000005];
scanf("%s",x); string s = x;
return s;
}
inline string uppercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
return s;
}
inline string lowercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
return s;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// Link --> https://oj.uz/problem/view/JOI18_bitaro
// Explanation --> https://codeforces.com/blog/entry/58433#:~:text=Sqrt%20decomposition.,cities%20with%20sorting).
int main()
{
const int B_SIZE = 150;
takei2(n,m); takei(q);
vvi adj(n+1), rev_adj(n+1);
rep(i,m)
{
takei2(u,v);
adj[u].pb(v);
rev_adj[v].pb(u);
}
vector<vector<pii>> v(n+1);
vi ptr(n+1);
vector<bool> vis(n+1 , 0);
repn(i,n)
{
priority_queue<vi> pq;
for(auto prev : rev_adj[i])
{
ptr[prev] = 0;
vpii &tmp = v[prev];
int &pos = ptr[prev];
if(pos < sz(tmp)) pq.push({tmp[pos].ff , tmp[pos].ss , prev});
}
vpii &curr = v[i];
while(!pq.empty() and sz(curr) != B_SIZE)
{
vi vec = pq.top();
pq.pop();
int d = vec[0] , start = vec[1] , prev = vec[2];
if(!vis[start]) curr.pb({d+1 , start});
vis[start] = 1;
vpii &tmp = v[prev];
int &pos = ++ptr[prev];
while(pos < sz(tmp) and vis[tmp[pos].ss]) pos++;
if(pos < sz(tmp)) pq.push({tmp[pos].ff , tmp[pos].ss , prev});
}
if(sz(curr) < B_SIZE) curr.pb({0,i});
// Resetting visited array
for(auto pr : curr) vis[pr.ss] = 0;
}
while(q--)
{
takei2(t,cnt);
vector<bool> avail(n+1, 1);
rep(i,cnt) {takei(x); avail[x] = 0;}
if(cnt >= B_SIZE) // HEAVY SET --> Brute Force (DP)
{
vi dp(n+1, -1);
dp[t] = 0;
for (int i = t-1; i >= 1; i--)
{
int tmp = -1;
for(auto nxt : adj[i])
{
if(dp[nxt] != -1) tmp = max(tmp , dp[nxt]+1);
}
dp[i] = tmp;
}
int ans = -1;
repn(i,n) if(avail[i]) ans = max(ans , dp[i]);
pi(ans);
}
else // LIGHT SET --> Find answer from PRECOMPUTED INFO
{
int ans = -1;
for(auto pr : v[t])
{
int d = pr.ff, start = pr.ss;
if(avail[start]) ans = max(ans , d);
}
pi(ans);
}
}
return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Compilation message (stderr)
bitaro.cpp: In function 'std::string uppercase(std::string)':
bitaro.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bitaro.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
bitaro.cpp:138:3: note: in expansion of macro 'rep'
138 | rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
| ^~~
bitaro.cpp: In function 'std::string lowercase(std::string)':
bitaro.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bitaro.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
bitaro.cpp:144:3: note: in expansion of macro 'rep'
144 | rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
| ^~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bitaro.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
bitaro.cpp:159:3: note: in expansion of macro 'rep'
159 | rep(i,m)
| ^~~
bitaro.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
bitaro.cpp:48:19: note: in expansion of macro 'loope'
48 | #define repn(i,n) loope(i,1,n)
| ^~~~~
bitaro.cpp:169:3: note: in expansion of macro 'repn'
169 | repn(i,n)
| ^~~~
bitaro.cpp:42:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
42 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
bitaro.cpp:47:18: note: in expansion of macro 'loop'
47 | #define rep(i,n) loop(i,0,n)
| ^~~~
bitaro.cpp:208:5: note: in expansion of macro 'rep'
208 | rep(i,cnt) {takei(x); avail[x] = 0;}
| ^~~
bitaro.cpp:43:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
43 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
bitaro.cpp:48:19: note: in expansion of macro 'loope'
48 | #define repn(i,n) loope(i,1,n)
| ^~~~~
bitaro.cpp:224:9: note: in expansion of macro 'repn'
224 | repn(i,n) if(avail[i]) ans = max(ans , dp[i]);
| ^~~~
bitaro.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
bitaro.cpp:157:3: note: in expansion of macro 'takei2'
157 | takei2(n,m); takei(q);
| ^~~~~~
bitaro.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
bitaro.cpp:68:25: note: in expansion of macro 'si'
68 | #define takei(a) int a; si(a)
| ^~
bitaro.cpp:157:16: note: in expansion of macro 'takei'
157 | takei2(n,m); takei(q);
| ^~~~~
bitaro.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
bitaro.cpp:161:5: note: in expansion of macro 'takei2'
161 | takei2(u,v);
| ^~~~~~
bitaro.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | #define si2(x,y) scanf("%d %d",&x,&y)
| ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:69:30: note: in expansion of macro 'si2'
69 | #define takei2(a,b) int a,b; si2(a,b)
| ^~~
bitaro.cpp:206:5: note: in expansion of macro 'takei2'
206 | takei2(t,cnt);
| ^~~~~~
bitaro.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define si(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
bitaro.cpp:68:25: note: in expansion of macro 'si'
68 | #define takei(a) int a; si(a)
| ^~
bitaro.cpp:208:17: note: in expansion of macro 'takei'
208 | rep(i,cnt) {takei(x); avail[x] = 0;}
| ^~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
