Submission #1552031
Source Code Expand
#include <bits/stdc++.h>
#define INF 1000000000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
struct edge{
int f,t,c;
edge(){}
edge(int ff,int tt,int cc){
f=ff;
t=tt;
c=cc;
}
};
int n,m;
int p[1001];
int q[1001];
ll dist[2005];
vector<edge> es;
int main(void){
scanf("%d%d",&n,&m);
int zero=2*n;
for(int i=0;i<n;i++){
scanf("%d",&p[i]);
es.push_back(edge(zero,i,p[i]));
es.push_back(edge(i,zero,0));
}
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
es.push_back(edge(n+i,zero,q[i]));
es.push_back(edge(zero,i+n,0));
}
for(int i=0;i<m;i++){
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
x--;
y--;
es.push_back(edge(y+n,x,b));
es.push_back(edge(x,y+n,-a));
}
for(int i=0;i<2*n;i++){
dist[i]=INF;
}
for(int i=0;i<=2*n+1;i++){
bool update=false;
for(int j=0;j<es.size();j++){
if(dist[es[j].f]!=INF && (ll)dist[es[j].f]+es[j].c<dist[es[j].t]){
dist[es[j].t]=(ll)dist[es[j].f]+es[j].c;
update=true;
}
}
if(!update)break;
if(i==2*n+1){
printf("no\n");
return 0;
}
}
printf("yes\n");
return 0;
}
Submission Info
Submission Time |
|
Task |
H - Asteroids2 |
User |
ryoissy |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
1156 Byte |
Status |
AC |
Exec Time |
1677 ms |
Memory |
4980 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:24:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
./Main.cpp:27:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&p[i]);
^
./Main.cpp:32:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q[i]);
^
./Main.cpp:38:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&x,&y,&a,&b);
^
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 |
4 ms |
704 KB |
10-small_yes-07 |
AC |
4 ms |
832 KB |
10-small_yes-08 |
AC |
4 ms |
704 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 |
1 ms |
256 KB |
20-small_disturb-06 |
AC |
20 ms |
832 KB |
20-small_disturb-07 |
AC |
21 ms |
704 KB |
20-small_disturb-08 |
AC |
20 ms |
704 KB |
30-large_yes-00 |
AC |
33 ms |
3444 KB |
30-large_yes-01 |
AC |
32 ms |
4340 KB |
30-large_yes-02 |
AC |
33 ms |
3444 KB |
30-large_yes-03 |
AC |
33 ms |
4852 KB |
30-large_yes-04 |
AC |
33 ms |
3956 KB |
40-large_disturb-00 |
AC |
1656 ms |
4724 KB |
40-large_disturb-01 |
AC |
1652 ms |
4980 KB |
40-large_disturb-02 |
AC |
1672 ms |
3444 KB |
40-large_disturb-03 |
AC |
1657 ms |
4724 KB |
40-large_disturb-04 |
AC |
1664 ms |
3444 KB |
40-large_disturb-05 |
AC |
1653 ms |
4468 KB |
40-large_disturb-06 |
AC |
1677 ms |
3444 KB |
40-large_disturb-07 |
AC |
1658 ms |
4596 KB |
40-large_disturb-08 |
AC |
1650 ms |
4084 KB |
40-large_disturb-09 |
AC |
1670 ms |
3444 KB |
40-large_disturb-10 |
AC |
1649 ms |
4468 KB |
40-large_disturb-11 |
AC |
1673 ms |
3444 KB |
40-large_disturb-12 |
AC |
1652 ms |
4340 KB |
40-large_disturb-13 |
AC |
1647 ms |
4212 KB |
40-large_disturb-14 |
AC |
1644 ms |
4596 KB |
40-large_disturb-15 |
AC |
1659 ms |
4724 KB |