이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
const int b = 100;
set<pair<int,int> > st[maxn];
vector<int>ig[maxn], g[maxn];
vector<int>order;
int n, m, q;
bool blocked[maxn];
bool visited[maxn];
int dp[maxn];
void dfs(int node) {
if(visited[node]) return;
visited[node] = true;
for(int i:ig[node]) {
if(!visited[i]) {
dfs(i);
}
}
order.pb(node);
}
int brute_force(int node) {
dfs(node);
reverse(order.begin(), order.end());
int result = -1;
for(int i=0;i<order.size();i++) {
int node=order[i];
for(int i:g[node]) {
if(!visited[i]) continue;
dp[node] = max(dp[node], dp[i] + 1);
}
//cout<<node<<": "<<dp[node]<<"\n";
if(!blocked[node])
result = max(result, dp[node]);
}
memset(dp, 0, sizeof(dp));
memset(visited,false,sizeof(visited));
order.clear();
return result;
}
void preprocess() {
for(int node=1;node<=n;node++) {
st[node].insert(mp(0, node));
map<int, int> dists;
for(int i:ig[node]) {
//update st[node] with values from st[i] + 1
// Possible optimization point, in case of TLE
for(auto vals:st[i]) {
dists[vals.second] = max(dists[vals.second], vals.first + 1);
}
}
for(auto i:dists) {
st[node].insert(mp(i.second, i.first));
if(st[node].size() > b) st[node].erase(st[node].begin());
}
}
}
void solve() {
int node, qs, x;
vector<int>points;
cin>>node>>qs;
for(int i=0;i<qs;i++) {
cin>>x;
points.pb(x);
blocked[x] = true;
}
if(qs >= b) {
cout<<brute_force(node);
for(int i:points) blocked[i] = false;
return;
}
int maxtunnels = -1;
for(auto i:st[node]) {
if(!blocked[i.second]) maxtunnels = max(maxtunnels, i.first);
}
cout<<maxtunnels<<"\n";
for(int i:points) blocked[i] = false;
}
int main() {
cin>>n>>m>>q;
int a, b;
for(int i=0;i<m;i++) {
cin>>a>>b;
g[a].pb(b);
ig[b].pb(a);
}
preprocess();
while(q--) {
solve();
}
}
컴파일 시 표준 에러 (stderr) 메시지
bitaro.cpp: In function 'int brute_force(int)':
bitaro.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<order.size();i++) {
~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |