| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 492202 | Malheiros | Bitaro’s Party (JOI18_bitaro) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
//#define int ll
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
#define PB push_back
#define MP make_pair
#define all(cont) cont.begin(),cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define FOR(i, j) for(int i=0;i<j;i++)
#define RFOR(i, j) for (int i=j;i>=0;i--)
#define GO cin.tie(NULL);
#define FAST ios_base::sync_with_stdio(false);
#define prec(x) cout << fixed << setprecision(x)
#define sz(x) (int)x.size()
typedef pair<int,int> pii;
typedef vector<int> VI;
typedef vector<pii> VPII;
typedef vector<VI> VVI;
typedef priority_queue<int> max_heap;
typedef priority_queue<pii> max_heapii;
typedef priority_queue<int,VI,greater<int>> min_heap;
typedef priority_queue<pii,VPII,greater<pii>> min_heapii;
const long double PI = 3.14159265359;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b){return uniform_int_distribution<ll>(a, b)(rng);}
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cout << vars << " = ";
string delim = "";
(..., (cout << delim << values, delim = ", "));
cout<<endl;
}
void print(vector<int>v){
cout<<"[";
FOR(i,v.size()){
cout<<v[i];
if(i+1!=v.size())cout<<", ";
}
cout<<"]"<<endl;
}
void print(pii p){
cout<<"{"<<p.first<<", "<<p.second<<"}"<<endl;
}
const int maxn=1e5+10;
const int magic=0;
VI grafo[maxn];
vector<pair<VI,int>> light[maxn];
vector<pair<set<int>,int>> heavy[maxn];
int ans[maxn];
VI caches[maxn];
int n,m,q;
void solvelight(){
}
int dist[maxn];
void solveheavy(int u){
//deb(u);
FOR(i,u+1)dist[i]=0;
//memset(dist,0,sizeof(dist));
for(int i=u;i>=0;i--){
for(auto k:grafo[i])dist[k]=max(dist[k],dist[i]+1);
}
/* FOR(i,u+1){
cout<<dist[i]<<' ';
}
cout<<endl;*/
}
void solveheavy(int u,const pair<unordered_set<int>,int> &cara){
// deb(u,);
int maior=0;
for(int i=u;i>=0;i--){
if(cara.first.find(i)==cara.first.end())maior=max(maior,dist[i]);
}
ans[cara.second]=maior;
}
void solveheavy(){
FOR(i,n){
if(!heavy[i].empty()){
solveheavy(i);
for(auto& k:heavy[i]){
solveheavy(i,k);
}
}
}
}
signed main(){
GO FAST
cin>>n>>m>>q;
FOR(i,m){
int a,b;cin>>a>>b;a--;b--;
grafo[b].PB(a);
}
FOR(i,q){
int f,k;
cin>>f>>k;
f--;
if (k>=magic){
set<int> sett;
FOR(j,k){
int a;cin>>a;a--;
sett.insert(a);
}
heavy[f].PB(MP(sett,i));
}
else{
VI v(k);
FOR(j,k){
cin>>v[j];
v[j]--;
}
light[f].PB(MP(v,i));
}
}
solvelight();
solveheavy();
FOR(i,q){
cout<<ans[i]<<'\n';
}
}