Submission #411680

#	Time	Username	Problem	Language	Result	Execution time	Memory
411680		Dormi	Travelling Merchant (CCO21_day2problem1)	C++14	25 / 25	1897 ms	29112 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template <typename T>
int sz(const T &a){return int(a.size());}
const int MN=2e5+1;
vector<pair<int,pll>> adj[MN];
bool gone[MN];
ll tried[MN];
ll work[MN];
bool dfs(int loc, ll am){
    if(am<=tried[loc])return false;
    if(am>=work[loc])return true;
    gone[loc]=true;
    for(auto x:adj[loc]){
        if(x.second.first<=am){
            if(gone[x.first]){
                gone[loc]=false;
                work[loc]=am;
                return true;
            }
            if(dfs(x.first,am+x.second.second)){
                gone[loc]=false;
                work[loc]=am;
                return true;
            }
        }
    }
    tried[loc]=am;
    gone[loc]=false;
    return false;
}
int main(int argc, char *argv[]) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,m,a,b;
    cin>>n>>m;
    ll r,p;
    for(int i=0;i<m;i++){
        cin>>a>>b>>r>>p;
        adj[a].push_back({b,{r,p}});
    }
    for(int i=1;i<=n;i++)tried[i]=-1,work[i]=LLONG_MAX;
    for(int i=1;i<=n;i++){
        ll lo=0,hi=1e9;
        while(lo!=hi){
            ll mid=(lo+hi)/2;
            if(dfs(i,mid))hi=mid;
            else lo=mid+1;
        }
        if(lo==1e9)printf("-1%c"," \n"[i==n]);
        else printf("%lli%c",lo," \n"[i==n]);
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16