oj.uz

Submission #446576

# Submission time Handle Problem Language Result Execution time Memory
446576 2021-07-22T13:17:18 Z keta_tsimakuridze Paths (BOI18_paths) C++14
100 / 100
 733 ms 79840 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int N=3e5+5,mod=1e9+7;
int t,n,m,k,cnt[N],col[N];
vector<pair<int,ll> > en[34];
vector<int> V[N][6];
 main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>col[i];
		col[i]--;
		V[0][col[i]].push_back(i);
	}
	for(int i=1;i<=m;i++) {
		int u,v;
		cin>>u>>v;
		V[u][col[v]].push_back(v);
		V[v][col[u]].push_back(u);
	}
	en[0].push_back({0,1});
	ll ans = -n;
	for(int i = 1; i<(1<<k); i++) {
		for(int j=1;j<=n;j++) cnt[j] = 0;
		for(int j=0;j<k;j++) {
			if(!((1<<j) & i)) continue;
			int b = i ^ (1<<j);
			for(int k=0; k<en[b].size(); k++){
				int u = en[b][k].f;
				for(int p=0; p<V[u][j].size(); p++) {
					cnt[V[u][j][p]] += en[b][k].s;
				}
			}
		}
		for(int j=1;j<=n;j++) {
			if(cnt[j]) en[i].push_back({j,cnt[j]}), ans += cnt[j];
		}
	}
	cout<<ans;
}

Compilation message

paths.cpp:10:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 |  main(){
      |  ^~~~
paths.cpp: In function 'int main()':
paths.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for(int k=0; k<en[b].size(); k++){
      |                 ~^~~~~~~~~~~~~
paths.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int p=0; p<V[u][j].size(); p++) {
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 42624 KB Output is correct
2 Correct 25 ms 42568 KB Output is correct
3 Correct 24 ms 42584 KB Output is correct
4 Correct 25 ms 42564 KB Output is correct
5 Correct 25 ms 42580 KB Output is correct
6 Correct 29 ms 42576 KB Output is correct
7 Correct 25 ms 42572 KB Output is correct
8 Correct 26 ms 42472 KB Output is correct
9 Correct 25 ms 42572 KB Output is correct
10 Correct 25 ms 42528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 47332 KB Output is correct
2 Correct 187 ms 46036 KB Output is correct
3 Correct 603 ms 73464 KB Output is correct
4 Correct 309 ms 48832 KB Output is correct
5 Correct 301 ms 47944 KB Output is correct
6 Correct 483 ms 68652 KB Output is correct
7 Correct 608 ms 73468 KB Output is correct
8 Correct 612 ms 73764 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 42624 KB Output is correct
2 Correct 25 ms 42568 KB Output is correct
3 Correct 24 ms 42584 KB Output is correct
4 Correct 25 ms 42564 KB Output is correct
5 Correct 25 ms 42580 KB Output is correct
6 Correct 29 ms 42576 KB Output is correct
7 Correct 25 ms 42572 KB Output is correct
8 Correct 26 ms 42472 KB Output is correct
9 Correct 25 ms 42572 KB Output is correct
10 Correct 25 ms 42528 KB Output is correct
11 Correct 238 ms 47332 KB Output is correct
12 Correct 187 ms 46036 KB Output is correct
13 Correct 603 ms 73464 KB Output is correct
14 Correct 309 ms 48832 KB Output is correct
15 Correct 301 ms 47944 KB Output is correct
16 Correct 483 ms 68652 KB Output is correct
17 Correct 608 ms 73468 KB Output is correct
18 Correct 612 ms 73764 KB Output is correct
19 Correct 230 ms 47300 KB Output is correct
20 Correct 188 ms 46124 KB Output is correct
21 Correct 607 ms 73276 KB Output is correct
22 Correct 295 ms 48828 KB Output is correct
23 Correct 293 ms 47996 KB Output is correct
24 Correct 478 ms 68768 KB Output is correct
25 Correct 609 ms 73392 KB Output is correct
26 Correct 609 ms 73880 KB Output is correct
27 Correct 191 ms 46208 KB Output is correct
28 Correct 255 ms 48284 KB Output is correct
29 Correct 709 ms 79840 KB Output is correct
30 Correct 554 ms 70188 KB Output is correct
31 Correct 604 ms 74280 KB Output is correct
32 Correct 733 ms 79816 KB Output is correct
33 Correct 26 ms 42572 KB Output is correct
34 Correct 25 ms 42508 KB Output is correct
35 Correct 26 ms 42580 KB Output is correct
36 Correct 26 ms 42584 KB Output is correct
37 Correct 25 ms 42572 KB Output is correct
38 Correct 26 ms 42540 KB Output is correct
39 Correct 25 ms 42572 KB Output is correct
40 Correct 27 ms 42508 KB Output is correct
41 Correct 25 ms 42512 KB Output is correct
42 Correct 25 ms 42576 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42444 KB Output is correct
2 Correct 84 ms 44116 KB Output is correct
3 Correct 79 ms 44100 KB Output is correct
4 Correct 198 ms 53084 KB Output is correct
5 Correct 156 ms 53180 KB Output is correct
6 Correct 235 ms 57496 KB Output is correct
7 Correct 83 ms 43716 KB Output is correct
8 Correct 220 ms 54768 KB Output is correct
9 Correct 165 ms 53584 KB Output is correct
10 Correct 195 ms 57140 KB Output is correct
11 Correct 185 ms 54936 KB Output is correct
12 Correct 179 ms 53972 KB Output is correct
13 Correct 205 ms 55396 KB Output is correct
14 Correct 238 ms 57532 KB Output is correct
15 Correct 243 ms 55436 KB Output is correct
16 Correct 26 ms 42476 KB Output is correct
17 Correct 25 ms 42552 KB Output is correct
18 Correct 25 ms 42484 KB Output is correct
19 Correct 25 ms 42532 KB Output is correct
20 Correct 25 ms 42572 KB Output is correct
21 Correct 28 ms 42572 KB Output is correct
22 Correct 26 ms 42556 KB Output is correct
23 Correct 25 ms 42504 KB Output is correct
24 Correct 25 ms 42568 KB Output is correct
25 Correct 26 ms 42580 KB Output is correct