Submission #1556699
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#define INF 112000000012345678LL
template<class T>
bool bellmanFord(const vector<vector<pair<int,T>>> &vec, vector<T> &d, int from=0){
fill(all(d), INF);
d[from] = 0;
int n = d.size();
rep(_,n){
bool update = false;
rep(i,n){
for(auto &p : vec[i]){
int to = p.first;
T nd = d[i] + p.second;
if(d[to] > nd){
d[to] = nd;
update = true;
}
}
}
if(!update) return true;
}
return false;
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<pair<int,long>>> vec(2*n+1);
vector<int> p(n), q(n);
rep(i,n) cin>>p[i];
rep(i,n) cin>>q[i];
// -p[i] : i*2
// q[i] : i*2+1
// zero : 2*n
rep(i,n){
vec[2*n].pb(mp(2*i, 0));
vec[2*i].pb(mp(2*n, p[i]));
vec[2*n].pb(mp(2*i+1, q[i]));
vec[2*i+1].pb(mp(2*n, 0));
}
rep(i,m){
int x,y,a,b;
cin>>x>>y>>a>>b;
x--;y--;
vec[2*y+1].pb(mp(2*x, -a));
vec[2*x].pb(mp(2*y+1, b));
}
vector<long> dd(2*n+1);
if(bellmanFord(vec, dd, 2*n)) cout << "yes" << endl;
else cout << "no" << endl;
// dbg(dd);
return 0;
}
Submission Info
Submission Time |
|
Task |
H - Asteroids2 |
User |
tossy |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
2076 Byte |
Status |
AC |
Exec Time |
1863 ms |
Memory |
4736 KB |
Judge Result
Set Name |
All |
Score / Max Score |
200 / 200 |
Status |
|
Set Name |
Test Cases |
All |
00-sample-00, 00-sample-01, 10-small_yes-00, 10-small_yes-01, 10-small_yes-02, 10-small_yes-03, 10-small_yes-04, 10-small_yes-05, 10-small_yes-06, 10-small_yes-07, 10-small_yes-08, 20-small_disturb-00, 20-small_disturb-01, 20-small_disturb-02, 20-small_disturb-03, 20-small_disturb-04, 20-small_disturb-05, 20-small_disturb-06, 20-small_disturb-07, 20-small_disturb-08, 30-large_yes-00, 30-large_yes-01, 30-large_yes-02, 30-large_yes-03, 30-large_yes-04, 40-large_disturb-00, 40-large_disturb-01, 40-large_disturb-02, 40-large_disturb-03, 40-large_disturb-04, 40-large_disturb-05, 40-large_disturb-06, 40-large_disturb-07, 40-large_disturb-08, 40-large_disturb-09, 40-large_disturb-10, 40-large_disturb-11, 40-large_disturb-12, 40-large_disturb-13, 40-large_disturb-14, 40-large_disturb-15 |
Case Name |
Status |
Exec Time |
Memory |
00-sample-00 |
AC |
1 ms |
256 KB |
00-sample-01 |
AC |
1 ms |
256 KB |
10-small_yes-00 |
AC |
1 ms |
256 KB |
10-small_yes-01 |
AC |
1 ms |
256 KB |
10-small_yes-02 |
AC |
1 ms |
256 KB |
10-small_yes-03 |
AC |
1 ms |
256 KB |
10-small_yes-04 |
AC |
1 ms |
256 KB |
10-small_yes-05 |
AC |
1 ms |
256 KB |
10-small_yes-06 |
AC |
11 ms |
640 KB |
10-small_yes-07 |
AC |
11 ms |
640 KB |
10-small_yes-08 |
AC |
11 ms |
640 KB |
20-small_disturb-00 |
AC |
1 ms |
256 KB |
20-small_disturb-01 |
AC |
1 ms |
256 KB |
20-small_disturb-02 |
AC |
1 ms |
256 KB |
20-small_disturb-03 |
AC |
1 ms |
256 KB |
20-small_disturb-04 |
AC |
1 ms |
256 KB |
20-small_disturb-05 |
AC |
2 ms |
256 KB |
20-small_disturb-06 |
AC |
26 ms |
640 KB |
20-small_disturb-07 |
AC |
25 ms |
640 KB |
20-small_disturb-08 |
AC |
25 ms |
640 KB |
30-large_yes-00 |
AC |
104 ms |
4736 KB |
30-large_yes-01 |
AC |
106 ms |
4736 KB |
30-large_yes-02 |
AC |
105 ms |
4736 KB |
30-large_yes-03 |
AC |
106 ms |
4736 KB |
30-large_yes-04 |
AC |
104 ms |
4736 KB |
40-large_disturb-00 |
AC |
1825 ms |
4736 KB |
40-large_disturb-01 |
AC |
1835 ms |
4736 KB |
40-large_disturb-02 |
AC |
1816 ms |
4736 KB |
40-large_disturb-03 |
AC |
1827 ms |
4736 KB |
40-large_disturb-04 |
AC |
1830 ms |
4736 KB |
40-large_disturb-05 |
AC |
1825 ms |
4736 KB |
40-large_disturb-06 |
AC |
1823 ms |
4736 KB |
40-large_disturb-07 |
AC |
1820 ms |
4736 KB |
40-large_disturb-08 |
AC |
1863 ms |
4736 KB |
40-large_disturb-09 |
AC |
1826 ms |
4736 KB |
40-large_disturb-10 |
AC |
1849 ms |
4736 KB |
40-large_disturb-11 |
AC |
1821 ms |
4736 KB |
40-large_disturb-12 |
AC |
1832 ms |
4736 KB |
40-large_disturb-13 |
AC |
1845 ms |
4736 KB |
40-large_disturb-14 |
AC |
1828 ms |
4736 KB |
40-large_disturb-15 |
AC |
1833 ms |
4736 KB |