Submission #72540684

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+5;
const ll INF=1e18;

int n,m,L,S,T;
vector<pair<int,int>> g[N];
vector<pair<ll,ll>> intervals[N][11]; 
vector<pair<ll,ll>> merge_intervals(vector<pair<ll,ll>>& intervals_vec){
    if(intervals_vec.empty())return {};
    sort(intervals_vec.begin(),intervals_vec.end());
    vector<pair<ll,ll>> res;
    ll l=intervals_vec[0].first,r=intervals_vec[0].second;
    for(int i=1;i<intervals_vec.size();i++){
        if(intervals_vec[i].first<=r+1){
            r=max(r,intervals_vec[i].second);
        }else{
            res.push_back({l,r});
            l=intervals_vec[i].first;
            r=intervals_vec[i].second;
        }
    }
    res.push_back({l,r});
    return res;
}
bool check_intersection(vector<pair<ll,ll>>& intervals_vec,ll S,ll T){
    for(auto &[l,r]:intervals_vec){
        if(!(r<S||l>T))return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>L>>S>>T;
    
    for(int i=1;i<=m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
    }
    
    intervals[1][0].push_back({0,0});
    
    for(int step=0;step<L;step++){
        for(int u=1;u<=n;u++){
            if(!intervals[u][step].empty()){
                intervals[u][step]=merge_intervals(intervals[u][step]);
            }
        }
        for(int u=1;u<=n;u++){
            if(intervals[u][step].empty())continue;
            
            for(auto &[v,c]:g[u]){
                for(auto &[l,r]:intervals[u][step]){
                    ll new_l=l+c;
                    ll new_r=min((ll)T,r+c);
                    if(new_l<=new_r){
                        intervals[v][step+1].push_back({new_l,new_r});
                    }
                }
            }
        }
    }
    for(int v=1;v<=n;v++){
        if(!intervals[v][L].empty()){
            intervals[v][L]=merge_intervals(intervals[v][L]);
        }
    }
    
    vector<int> ans;
    for(int v=1;v<=n;v++){
        if(check_intersection(intervals[v][L],S,T)){
            ans.push_back(v);
        }
    }
    
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++){
        if(i)cout<<" ";
        cout<<ans[i];
    }
    cout<<"\n";
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'std::vector<std::pair<long long int, long long int> > merge_intervals(std::vector<std::pair<long long int, long long int> >&)':
./Main.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=1;i<intervals_vec.size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~
./Main.cpp: In function 'int main()':
./Main.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~

Judge Result