oj.uz

Submission #748454

# Submission time Handle Problem Language Result Execution time Memory
748454 2023-05-26T10:06:17 Z mariowong Paths (BOI18_paths) C++14
100 / 100
 2418 ms 221228 KB 
#include <bits/stdc++.h>
using namespace std;
 
int n,m,colour[300005],u,v,k,ct,len;
vector <int> ans[300005];
long long anss;
vector <int> edge[300005],now;
string pattern[335],r;
unordered_map <string,int> indx;
bool cmp(string a1,string a2){
	return (a1.length() < a2.length() || (a1.length() == a2.length() && a1 < a2));
}
int main() {
	ios::sync_with_stdio(false); 
	cin >> n >> m >> k;
	indx.reserve(500);
	for (int i=1;i<=n;i++){
		cin >> colour[i];
	} 
	for (int i=1;i<=m;i++){
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for (int i=1;i<(1<<k);i++){
		now.clear();
		for (int j=0;j<k;j++){
			if ((i&(1<<j)) > 0)
			now.push_back(j+1);
		}
		do{
			ct++;
			for (int i=0;i<now.size();i++){
				pattern[ct]+=char(now[i]+'0');
			}
		}while (next_permutation(now.begin(),now.end()));
	}
	sort(pattern+1,pattern+1+ct,cmp);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=ct+1;j++){
			ans[i].push_back(0);
		}
	}
	for (int i=1;i<=ct;i++){
		indx[pattern[i]]=i;
		for (int j=1;j<=n;j++){
			if (pattern[i].length() == 1 && colour[j] == pattern[i][0]-'0')
			ans[j][i]=1;
			else
			if (colour[j] == pattern[i][0]-'0'){
				r.clear(); len=pattern[i].length();
				for (int k=1;k<len;k++){
					r+=pattern[i][k];
				}
				for (int k=0;k<edge[j].size();k++){
					ans[j][i]+=ans[edge[j][k]][indx[r]];
				}	
			}
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=ct;j++){
			anss+=ans[i][j];
		}
	}
	cout << anss-n << "\n";
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for (int i=0;i<now.size();i++){
      |                 ~^~~~~~~~~~~
paths.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int k=0;k<edge[j].size();k++){
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14332 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14324 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 10 ms 14500 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 20908 KB Output is correct
2 Correct 93 ms 20192 KB Output is correct
3 Correct 666 ms 52044 KB Output is correct
4 Correct 117 ms 23244 KB Output is correct
5 Correct 102 ms 22716 KB Output is correct
6 Correct 435 ms 41988 KB Output is correct
7 Correct 688 ms 51912 KB Output is correct
8 Correct 701 ms 52700 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14332 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14324 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 9 ms 14420 KB Output is correct
8 Correct 10 ms 14500 KB Output is correct
9 Correct 8 ms 14420 KB Output is correct
10 Correct 8 ms 14428 KB Output is correct
11 Correct 111 ms 20908 KB Output is correct
12 Correct 93 ms 20192 KB Output is correct
13 Correct 666 ms 52044 KB Output is correct
14 Correct 117 ms 23244 KB Output is correct
15 Correct 102 ms 22716 KB Output is correct
16 Correct 435 ms 41988 KB Output is correct
17 Correct 688 ms 51912 KB Output is correct
18 Correct 701 ms 52700 KB Output is correct
19 Correct 124 ms 20796 KB Output is correct
20 Correct 90 ms 20256 KB Output is correct
21 Correct 717 ms 52008 KB Output is correct
22 Correct 123 ms 23340 KB Output is correct
23 Correct 102 ms 22784 KB Output is correct
24 Correct 492 ms 42004 KB Output is correct
25 Correct 694 ms 52116 KB Output is correct
26 Correct 726 ms 52576 KB Output is correct
27 Correct 234 ms 20396 KB Output is correct
28 Correct 386 ms 25928 KB Output is correct
29 Correct 2160 ms 183556 KB Output is correct
30 Correct 1317 ms 102284 KB Output is correct
31 Correct 1371 ms 102360 KB Output is correct
32 Correct 2240 ms 183464 KB Output is correct
33 Correct 8 ms 14420 KB Output is correct
34 Correct 9 ms 14420 KB Output is correct
35 Correct 8 ms 14348 KB Output is correct
36 Correct 8 ms 14428 KB Output is correct
37 Correct 8 ms 14420 KB Output is correct
38 Correct 8 ms 14420 KB Output is correct
39 Correct 8 ms 14444 KB Output is correct
40 Correct 8 ms 14432 KB Output is correct
41 Correct 8 ms 14420 KB Output is correct
42 Correct 8 ms 14420 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 291 ms 17256 KB Output is correct
3 Correct 35 ms 16268 KB Output is correct
4 Correct 166 ms 26788 KB Output is correct
5 Correct 127 ms 27544 KB Output is correct
6 Correct 2298 ms 220904 KB Output is correct
7 Correct 80 ms 16400 KB Output is correct
8 Correct 519 ms 70624 KB Output is correct
9 Correct 411 ms 71372 KB Output is correct
10 Correct 509 ms 71236 KB Output is correct
11 Correct 1068 ms 118696 KB Output is correct
12 Correct 1368 ms 170356 KB Output is correct
13 Correct 1022 ms 118560 KB Output is correct
14 Correct 2179 ms 220924 KB Output is correct
15 Correct 2418 ms 221228 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 10 ms 14440 KB Output is correct
18 Correct 8 ms 14436 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 9 ms 14420 KB Output is correct
21 Correct 8 ms 14420 KB Output is correct
22 Correct 8 ms 14368 KB Output is correct
23 Correct 8 ms 14416 KB Output is correct
24 Correct 8 ms 14432 KB Output is correct
25 Correct 10 ms 14328 KB Output is correct