이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
const int N = 100001;
const int K = 300;
int n, m, q, vis1[N], vis2[N];
vector <int> v[N], g[N];
vector <pair <int, int> > f[N];
int curt;
vector <pair <int, int> > merge(vector <pair <int, int> > &l, vector <pair <int, int> > &r){
curt++;
vector <pair <int, int> > ret;
int lpos = 0, rpos = 0;
int lsz = l.size(), rsz = r.size();
while(ret.size() < K && (lpos < lsz || rpos < rsz)){
pair <int, int> winner;
if(lpos == lsz){
winner = make_pair(r[rpos].first + 1, r[rpos].second);
rpos++;
}
else if(rpos == rsz){
winner = l[lpos];
lpos++;
}
else if(l[lpos].first > r[rpos].first + 1){
winner = l[lpos];
lpos++;
}
else{
winner = make_pair(r[rpos].first + 1, r[rpos].second);
rpos++;
}
if(vis2[winner.second] == curt) continue;
vis2[winner.second] = curt;
ret.push_back(winner);
}
return ret;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for(int i = 0 ; i < m ; i++){
int x, y;
cin >> x >> y;
x--; y--;
v[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0 ; i < n ; i++){
f[i].push_back(make_pair(0, i));
for(auto &j : g[i]){
f[i] = merge(f[i], f[j]);
}
}
for(int i = 1 ; i <= q ; i++){
int t, sz;
cin >> t >> sz;
t--;
for(int j = 0 ; j < sz ; j++){
int x;
cin >> x;
x--;
vis1[x] = i;
}
//~ if(sz < K){
//~ int ans = -1;
//~ for(auto &j : f[t]){
//~ if(vis1[j.second] == i) continue;
//~ ans = j.first;
//~ break;
//~ }
//~ cout << ans << "\n";
//~ }
//~ else{
vector <int> ans(n, 0);
for(int j = 0 ; j <= t ; j++){
if(vis1[j] == i) continue;
for(auto &k : v[j]){
ans[k] = max(ans[k], 1 + ans[j]);
}
}
if(ans[t] == 0 && vis1[t] == i) cout << "-1\n";
else cout << ans[t] << "\n";
//~ }
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |