이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=2e5+5,inf = 0x3f3f3f3f;
struct edge{int v,r,p;};
int n,m,l[N],r[N];
vector <edge> G[N];
bool vis[N];
bool dfs(int u,int x){
if(x <= l[u])return 0;
if(x >= r[u])return 1;
vis[u] = 1;
for(auto &t:G[u]){
if(x >= t.r){
if(vis[t.v]){
vis[u] = 0,r[u] = x;
return 1;
}
if(dfs(t.v,min(inf,x + t.p))){
vis[u] = 0,r[u] = x;
return 1;
}
}
}
vis[u] = 0,l[u] = x;
return 0;
}
int main(){
n = read(),m = read();
rep(i,1,m){
int a = read(),b = read(),r = read(),p = read();
G[a].pb((edge){b,r,p});
}
rep(i,1,n)l[i] = -1,r[i] = inf;
rep(i,1,n){
int L = 0,R = inf;
while(L < R){
int mid = (L + R) >> 1;
if(dfs(i,mid))R = mid;
else L = mid+1;
}
if(L == inf)printf("-1%c"," \n"[i==n]);
else printf("%d%c",L," \n"[i==n]);
}
return 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... |