Submission #1654456
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);
template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
each(x,vec) is >> x;
return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
rep(i,vec.size()) {
if (i) os << " ";
os << vec[i];
}
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
rep(i,vec.size()) {
if (i) os << endl;
os << vec[i];
}
return os;
}
bool solve() {
ll n, m; cin >> n >> m;
vector<ll> p(n), q(n); cin >> p >> q;
vector<ll> X(m), Y(m), a(m), b(m);
rep(i, m) {
cin >> X[i] >> Y[i] >> a[i] >> b[i];
--X[i], --Y[i];
}
ll s = 2*n;
ll V = 2*n+1;
vector<vector<P>> G(V);
rep(i, n) G[s].pb(P(i, p[i]));
rep(i, n) G[n+i].pb(P(s, q[i]));
rep(i, m) {
G[X[i]].pb(P(n+Y[i], -a[i]));
G[n+Y[i]].pb(P(X[i], b[i]));
}
vector<ll> dist(V, linf);
dist[s] = 0;
rep(t, V+1) {
bool is_update = false;
rep(i, V) each(p, G[i]) {
if (dist[i] == linf) continue;
if (dist[i]+p.second < dist[p.first]) {
dist[p.first] = dist[i]+p.second;
is_update = true;
}
}
if (!is_update) break;
if (t == V) return false;
}
// cout << dist << endl;
rep(i, n) {
// xi >= 0
if (dist[i] < 0) return false;
// yi <= 0
if (dist[n+i] > 0) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
if (solve()) {
cout << "yes" << endl;
}
else {
cout << "no" << endl;
}
}
Submission Info
Submission Time |
|
Task |
H - Asteroids2 |
User |
drafear |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2508 Byte |
Status |
WA |
Exec Time |
771 ms |
Memory |
7936 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
WA |
1 ms |
256 KB |
10-small_yes-01 |
WA |
1 ms |
256 KB |
10-small_yes-02 |
WA |
1 ms |
256 KB |
10-small_yes-03 |
WA |
1 ms |
256 KB |
10-small_yes-04 |
WA |
1 ms |
256 KB |
10-small_yes-05 |
WA |
2 ms |
256 KB |
10-small_yes-06 |
AC |
5 ms |
1024 KB |
10-small_yes-07 |
AC |
5 ms |
1024 KB |
10-small_yes-08 |
AC |
5 ms |
1024 KB |
20-small_disturb-00 |
WA |
1 ms |
256 KB |
20-small_disturb-01 |
WA |
1 ms |
256 KB |
20-small_disturb-02 |
WA |
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 |
1 ms |
256 KB |
20-small_disturb-06 |
AC |
10 ms |
1024 KB |
20-small_disturb-07 |
AC |
10 ms |
1024 KB |
20-small_disturb-08 |
AC |
10 ms |
1024 KB |
30-large_yes-00 |
WA |
38 ms |
7936 KB |
30-large_yes-01 |
WA |
38 ms |
7936 KB |
30-large_yes-02 |
WA |
38 ms |
7936 KB |
30-large_yes-03 |
WA |
38 ms |
7936 KB |
30-large_yes-04 |
WA |
38 ms |
7936 KB |
40-large_disturb-00 |
AC |
765 ms |
7936 KB |
40-large_disturb-01 |
AC |
769 ms |
7936 KB |
40-large_disturb-02 |
AC |
760 ms |
7936 KB |
40-large_disturb-03 |
AC |
751 ms |
7936 KB |
40-large_disturb-04 |
AC |
765 ms |
7936 KB |
40-large_disturb-05 |
AC |
764 ms |
7936 KB |
40-large_disturb-06 |
AC |
754 ms |
7936 KB |
40-large_disturb-07 |
AC |
768 ms |
7936 KB |
40-large_disturb-08 |
AC |
766 ms |
7936 KB |
40-large_disturb-09 |
AC |
766 ms |
7936 KB |
40-large_disturb-10 |
AC |
761 ms |
7936 KB |
40-large_disturb-11 |
AC |
769 ms |
7936 KB |
40-large_disturb-12 |
AC |
760 ms |
7936 KB |
40-large_disturb-13 |
AC |
760 ms |
7936 KB |
40-large_disturb-14 |
AC |
771 ms |
7936 KB |
40-large_disturb-15 |
AC |
758 ms |
7936 KB |