Submission #8361665


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);
	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;
	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 0
Code Size 3444 Byte
Status RE
Exec Time 2104 ms
Memory 13568 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:110: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 0 / 600
Status
AC × 3
AC × 20
TLE × 10
RE × 10
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 4 ms 4352 KB
in02.txt AC 4 ms 4352 KB
in03.txt AC 4 ms 4352 KB
in04.txt AC 4 ms 4352 KB
in05.txt AC 4 ms 4352 KB
in06.txt AC 4 ms 4352 KB
in07.txt TLE 2103 ms 8832 KB
in08.txt TLE 2103 ms 8704 KB
in09.txt RE 133 ms 12928 KB
in10.txt RE 132 ms 12800 KB
in11.txt TLE 2103 ms 8704 KB
in12.txt TLE 2103 ms 10880 KB
in13.txt TLE 2104 ms 8960 KB
in14.txt TLE 2103 ms 8960 KB
in15.txt RE 132 ms 12928 KB
in16.txt RE 133 ms 12928 KB
in17.txt RE 133 ms 13056 KB
in18.txt RE 133 ms 13056 KB
in19.txt AC 82 ms 8832 KB
in20.txt AC 80 ms 8832 KB
in21.txt AC 85 ms 8960 KB
in22.txt AC 81 ms 8832 KB
in23.txt AC 57 ms 8960 KB
in24.txt AC 57 ms 8960 KB
in25.txt AC 57 ms 8960 KB
in26.txt TLE 2104 ms 9216 KB
in27.txt RE 135 ms 13568 KB
in28.txt RE 129 ms 13568 KB
in29.txt TLE 2104 ms 9216 KB
in30.txt TLE 2104 ms 9344 KB
in31.txt RE 140 ms 13440 KB
in32.txt RE 139 ms 13440 KB
in33.txt TLE 2104 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