Submission #2270834
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";} template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;} template<class T>void chmin(T&a,const T&b){if(a>b)a=b;} template<class T>void chmax(T&a,const T&b){if(a<b)a=b;} int nextInt() { int x; scanf("%d", &x); return x;} const int MAX_V = 2005; struct E { int to; ll w; }; vector<E> g[MAX_V]; int main2() { REP(i, MAX_V) g[i].clear(); int N = nextInt(); int M = nextInt(); int s = N + N; REP(i, N) { int p = nextInt(); g[s].push_back({ i, p }); g[i].push_back({s, 0}); } REP(i, N) { int q = nextInt(); g[N+i].push_back({ s, q }); g[s].push_back({N+i, 0}); } REP(k, M) { int x = nextInt() - 1; int y = nextInt() - 1; int a = nextInt(); int b = nextInt(); g[x].push_back({N+y, -a}); g[N+y].push_back({x, b}); } vector<ll> d(N + N + 1, 0); const int V = d.size(); bool neg_cycle = false; REP(step, 2 * V + 10) { bool update = false; REP(from, V) { for (const E e : g[from]) { if (d[e.to] > d[from] + e.w) { d[e.to] = d[from] + e.w; update = true; } } } if (!update) { break; } else { if (step >= 2 * V) { neg_cycle = true; break; } } } cout << (!neg_cycle ? "yes":"no") << endl; return 0; } int main() { for (;!cin.eof();cin>>ws) main2(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - Asteroids2 |
User | hs484 |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 1730 Byte |
Status | AC |
Exec Time | 1566 ms |
Memory | 6784 KB |
Compile Error
./Main.cpp: In function ‘int nextInt()’: ./Main.cpp:14:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int nextInt() { int x; scanf("%d", &x); return x;} ^
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 | 5 ms | 768 KB |
10-small_yes-07 | AC | 5 ms | 768 KB |
10-small_yes-08 | AC | 5 ms | 768 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 | 2 ms | 256 KB |
20-small_disturb-04 | AC | 2 ms | 256 KB |
20-small_disturb-05 | AC | 2 ms | 256 KB |
20-small_disturb-06 | AC | 16 ms | 768 KB |
20-small_disturb-07 | AC | 17 ms | 768 KB |
20-small_disturb-08 | AC | 16 ms | 768 KB |
30-large_yes-00 | AC | 45 ms | 4736 KB |
30-large_yes-01 | AC | 45 ms | 4736 KB |
30-large_yes-02 | AC | 45 ms | 4736 KB |
30-large_yes-03 | AC | 45 ms | 4736 KB |
30-large_yes-04 | AC | 45 ms | 4736 KB |
40-large_disturb-00 | AC | 1553 ms | 4736 KB |
40-large_disturb-01 | AC | 1555 ms | 4736 KB |
40-large_disturb-02 | AC | 1540 ms | 4736 KB |
40-large_disturb-03 | AC | 1523 ms | 4736 KB |
40-large_disturb-04 | AC | 1547 ms | 4736 KB |
40-large_disturb-05 | AC | 1547 ms | 4736 KB |
40-large_disturb-06 | AC | 1530 ms | 4736 KB |
40-large_disturb-07 | AC | 1562 ms | 4736 KB |
40-large_disturb-08 | AC | 1553 ms | 4736 KB |
40-large_disturb-09 | AC | 1554 ms | 4736 KB |
40-large_disturb-10 | AC | 1551 ms | 4736 KB |
40-large_disturb-11 | AC | 1566 ms | 4736 KB |
40-large_disturb-12 | AC | 1544 ms | 4736 KB |
40-large_disturb-13 | AC | 1538 ms | 4736 KB |
40-large_disturb-14 | AC | 1539 ms | 6784 KB |
40-large_disturb-15 | AC | 1542 ms | 4736 KB |