oj.uz

Submission #249189

# Submission time Handle Problem Language Result Execution time Memory
249189 2020-07-14T13:18:12 Z blacktulip Shell (info1cup18_shell) C++17
55 / 100
 1000 ms 43384 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,dp[1505][1505],vis[1505][1505];
int cev;
string s;
vector<int> v[li];

inline int add(int x,int y){
	if(x+y>=mod)return x+y-mod;
	return x+y;
}

inline int mul(int x,int y){
	return (x%mod)*(y%mod)%mod;
}

inline int f(int sira,int num){
	int cevv=0;
	if(sira==n){
		if(num<=k)return 0;
		return 1;
	}
	if(~dp[sira][num])return dp[sira][num];
	for(int i=0;i<(int)v[sira].size();i++){
		int go=v[sira][i];
		cevv=add(cevv,mul(f(go,num+(go==a[num]?1:0)),vis[sira][go]));
	}
	return dp[sira][num]=cevv;
}

main(void){
	memset(dp,-1,sizeof(dp));
	scanf("%lld %lld %lld",&n,&m,&k);
	for(int i=1;i<=k;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		
		scanf("%lld %lld",&x,&y);
		if(vis[x][y]){vis[x][y]++;continue;}
		v[x].pb(y);
		vis[x][y]++;
	}
	printf("%lld\n",f(1,1+(a[1]==1?1:0)));
	return 0;
}

Compilation message

shell.cpp:53:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
shell.cpp: In function 'int main()':
shell.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~
shell.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29824 KB Output is correct
2 Correct 19 ms 29824 KB Output is correct
3 Correct 17 ms 29824 KB Output is correct
4 Correct 17 ms 29952 KB Output is correct
5 Correct 19 ms 29848 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29824 KB Output is correct
2 Correct 19 ms 29824 KB Output is correct
3 Correct 17 ms 29824 KB Output is correct
4 Correct 17 ms 29952 KB Output is correct
5 Correct 19 ms 29848 KB Output is correct
6 Correct 17 ms 30208 KB Output is correct
7 Correct 73 ms 38656 KB Output is correct
8 Correct 59 ms 38016 KB Output is correct
9 Correct 33 ms 36864 KB Output is correct
10 Correct 40 ms 39420 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30336 KB Output is correct
2 Execution timed out 1097 ms 43384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29824 KB Output is correct
2 Correct 19 ms 29824 KB Output is correct
3 Correct 17 ms 29824 KB Output is correct
4 Correct 17 ms 29952 KB Output is correct
5 Correct 19 ms 29848 KB Output is correct
6 Correct 17 ms 30208 KB Output is correct
7 Correct 73 ms 38656 KB Output is correct
8 Correct 59 ms 38016 KB Output is correct
9 Correct 33 ms 36864 KB Output is correct
10 Correct 40 ms 39420 KB Output is correct
11 Correct 19 ms 30336 KB Output is correct
12 Execution timed out 1097 ms 43384 KB Time limit exceeded
13 Halted 0 ms 0 KB -