Submission #8362657


Source Code Expand

Copy
#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> trp;
typedef vector<ll> vi;
typedef vector<pll> vp;

#define fu(i,a,b)   for(ll i=a;i<=b;i++)
#define f1(i,n)     for(ll i=1;i<=n;i++)
#define fs(i,s)     for(ll i=0;i+1<=s.length();i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define fuv(i,a)    for(ll i=0;i<a.size();i++)
#define fdv(i,a)    for(ll i=(ll)a.size()-1;i>=0;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define uni(a)      (a).erase(unique(all(a)), (a).end())
#define pb(i)       push_back(i)
#define popb()      pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define pr(a)       cout<<a<<endl
#define pr2(a,b)    cout<<a<<" "<<b<<endl
#define rpr(a)      return cout<<a<<endl,0
#define prY         cout<<"YES"<<endl
#define prN         cout<<"NO"<<endl
#define bit(n,i)    (((n)>>(i))&1)
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)  lower_bound(all(a),x) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()		
#define ast(x,a,b)  assert(x>=a and x<=b)				
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define	mp3(a,b,c)  make_pair(a,make_pair(b,c))
#define se          second
#define fi          first 
#define sse         second.second
#define sfi         second.first
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline ll mnz(ll& a,ll b){return a=(a>b?b:a);}
inline ll mxz(ll& a,ll b){return a=(a<b?b:a);}
inline string toString(ll n) {stringstream ss; ss << n;return ss.str();}
double const eps = 1e-6;
ll const Base=998244353,oo=1e17,MAXN=1e5;


class node{
	public :ll val,l,r;
};
node segtree[4*MAXN+5];
void Init(ll x,ll l,ll r){
	segtree[x].val=oo;
	segtree[x].l=l;
	segtree[x].r=r;
	
	if(l==r)re;
	ll mid=(l+r)>>1LL;
	Init(x<<1,l,mid);
	Init((x<<1)|1,mid+1,r);
}

void inline Upd(ll x,ll u,ll v,ll val){
	if(u>segtree[x].r or v<segtree[x].l)re;
	if(u<=segtree[x].l and v>=segtree[x].r){
		mnz(segtree[x].val,val);
		re ;
	}
	Upd(x<<1,u,v,val);
	Upd((x<<1)|1,u,v,val);
}
ll inline Get(ll x,ll p){
	if(segtree[x].l>p or segtree[x].r<p)re oo;
	if(segtree[x].r==segtree[x].l)re segtree[x].val;
	re min(segtree[x].val,min(Get(x<<1,p),Get(((x<<1)|1),p)));
}
vp store[MAXN+5];
ll Solves(){
	
	ll n,m,k,cnt=0,ans=1,x,y,q,c,sum=0,v,t;
	// PROCESS IN HERE
	
	sc(n);
	sc(m);
	Init(1,1,n);
	Upd(1,1,1,0);
	while(m--){
		sc2(x,y); sc(c);
		store[x].pb(mp(y,c));
	}
	
	f1(i,n){
		v=Get(1,i);	
		fuv(j,store[i]){
			Upd(1,i,store[i][j].fi,v+store[i][j].se);
		}
	}
	c=Get(1,n);
	if(c==oo)c=-1;
	pr(c);
	re 0;
	// Hack it if you can :)
}

int main(){
	//INPUT;
	if(fopen("locin.txt", "r"))INPUT;
	ll JUDGE_ONLINE = 1;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll test=1;
//	sc(test);
	fu(T,1,test){
//		cout<<"Case #"<<T<<": ";
		Solves();
	}
	if (!JUDGE_ONLINE) cout << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";  
		
}

Submission Info

Submission Time
Task D - Shortest Path on a Line
User thidailoc
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3512 Byte
Status AC
Exec Time 82 ms
Memory 13568 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:114:34: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  if(fopen("locin.txt", "r"))INPUT;
                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 40
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt
All sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, sample01.txt, sample02.txt, sample03.txt
Case Name Status Exec Time Memory
in01.txt AC 3 ms 4352 KB
in02.txt AC 3 ms 4352 KB
in03.txt AC 3 ms 4352 KB
in04.txt AC 3 ms 4352 KB
in05.txt AC 3 ms 4352 KB
in06.txt AC 3 ms 4352 KB
in07.txt AC 64 ms 8832 KB
in08.txt AC 67 ms 8704 KB
in09.txt AC 78 ms 12928 KB
in10.txt AC 79 ms 12800 KB
in11.txt AC 60 ms 8704 KB
in12.txt AC 67 ms 8832 KB
in13.txt AC 69 ms 8960 KB
in14.txt AC 70 ms 8960 KB
in15.txt AC 81 ms 12928 KB
in16.txt AC 78 ms 12928 KB
in17.txt AC 82 ms 13056 KB
in18.txt AC 82 ms 13056 KB
in19.txt AC 58 ms 8832 KB
in20.txt AC 53 ms 8832 KB
in21.txt AC 57 ms 8960 KB
in22.txt AC 56 ms 8832 KB
in23.txt AC 58 ms 8960 KB
in24.txt AC 56 ms 8960 KB
in25.txt AC 54 ms 8960 KB
in26.txt AC 60 ms 9216 KB
in27.txt AC 50 ms 13568 KB
in28.txt AC 61 ms 13568 KB
in29.txt AC 58 ms 9216 KB
in30.txt AC 55 ms 9344 KB
in31.txt AC 53 ms 13440 KB
in32.txt AC 51 ms 13440 KB
in33.txt AC 58 ms 9088 KB
in34.txt AC 3 ms 4352 KB
sample01.txt AC 3 ms 4352 KB
sample02.txt AC 3 ms 4352 KB
sample03.txt AC 3 ms 4352 KB