이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define ld long double
#define int long long
#define forn(i,j) for(int i = 0; i < j; i++)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define rof(i,j) rof(int i = j; i >= 0; --i)
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define vvpii vector<vector<pii>>
#define vb vector<bool>
#define pb push_back
#define p push
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define qi queue<int>
#define qpii queue<pii>
#define pqpii priority_queue<pii>
#define pqi priority_queue<int>
#define MOD 1000000007
void setIO(string name = ""){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(!name.empty()){
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
vvi graph;
vi dist;
vi dt;
void dfs(int u){
for(int x : graph[u]){
dt[x] = max(dt[x],dt[u] + 1);
dfs(x);
}
}
bool comp(int &u, int &v){
return dist[u] > dist[v];
}
signed main(){
setIO();
int n,m,q;
cin >> n >> m >> q;
graph.resize(n);
dist.resize(n);
dist.assign(n,-1);
int h = sqrt(n);
forn(i,m){
int a,b;
cin >> a >> b;
a--;
b--;
graph[b].pb(a);
}
vvpii dp(n);
forn(i,n){
vi nodes;
dist[i] = 0;
nodes.pb(i);
vb used(n,false);
for(int x : graph[i]){
for(pii j : dp[x]){
if(!used[j.f]){
used[j.f] = true;
nodes.pb(j.f);
}
dist[j.f] = max(dist[j.f],j.s+1);
}
}
sort(all(nodes),comp);
for(int j : nodes){
if(dp[i].size() < h){
dp[i].pb({j,dist[j]});
dist[j] = 0;
}
else{
break;
}
}
}
while(q--){
vb deleted(n,false);
int ind,del;
cin >> ind >> del;
ind--;
forn(i,del){
int a;
cin >> a;
a--;
deleted[a] = true;
}
if(del <= h){
int ans = -1;
int k = 0;
for(pii j : dp[ind]){
if(!deleted[j.f]){
ans = max(ans,j.s);
k++;
}
if(k > 0){
break;
}
}
cout << ans << endl;
}
else{
dt.assign(n,-1);
dt[ind] = 0;
dfs(ind);
int ans = -1;
forn(i,n){
if(!deleted[i]){
ans = max(ans,dt[i]);
}
}
cout << ans << endl;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'int main()':
bitaro.cpp:105:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
105 | if(dp[i].size() < h){
| ~~~~~~~~~~~~~^~~
bitaro.cpp: In function 'void setIO(std::string)':
bitaro.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:43:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |