# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1116829 |
2024-11-22T12:54:43 Z |
0pt1mus23 |
Paths (BOI18_paths) |
C++14 |
|
175 ms |
27568 KB |
// #pragma GCC optimize("Ofast,unroll-loops")
// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 3e5+23, inf = INT_MAX, LG = 19,pr = 31;
vector<int> graph[sze];
int used[sze];
int var[6][6][6][6][6];
vector<int> ord;
int col[sze];
int dp[sze];
int nxt[sze];
void dfs(int node,int idx){
if(used[node]){
return;
}
used[node]=1;
if(idx== (ord.size()-1 )){
dp[node]=1;
return;
}
for(auto v:graph[node]){
if(col[v]==ord[idx+1]){
dfs(v,idx+1);
dp[node]+=dp[v];
}
}
}
vector<int> co[10];
void fast(){
int n,m,k;
cin>>n>>m>>k;
for(int i =1;i<=n;i++){
cin>>col[i];
co[col[i]].pb(i);
}
int u,v;
for(int i =0;i<m;i++){
cin>>u>>v;
graph[u].pb(v);
graph[v].pb(u);
}
int ans=0;
vector<int> ad;
for(int i =0;i<k;i++){
ad.pb(i+1);
}
int hash=0,pp;
// for(auto v:ad) cout<<v<<" ";cout<<endl;
do{
ord.clear();
vector<int> cc(5,0);
ord.pb(ad[0]);
cc[0]=ord[0];
for(int i =1;i<k;i++){
ord.pb(ad[i]);
cc[i]=ord[i];
if( !var[cc[0]][cc[1]][cc[2]][cc[3]][cc[4]] ){
// for(auto v:ord) cout<<v<<" ,";cout<<endl;
for(int j=1;j<=n;j++){
dp[j]=0;
used[j]=0;
}
for(auto v:co[ord[0]]){
dfs(v,0);
if(dp[v]){
// cout<<v<<" == "<<dp[v]<<endl;
ans=(ans+dp[v])%mod;
}
}
var[cc[0]][cc[1]][cc[2]][cc[3]][cc[4]]=1;
}
}
}while(next_permutation(all(ad)));
putr(ans);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
fast();
}
return 0;
}
Compilation message
paths.cpp: In function 'void dfs(long long int, long long int)':
paths.cpp:27:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if(idx== (ord.size()-1 )){
| ~~~^~~~~~~~~~~~~~~~~~
paths.cpp: In function 'void fast()':
paths.cpp:59:9: warning: unused variable 'hash' [-Wunused-variable]
59 | int hash=0,pp;
| ^~~~
paths.cpp:59:16: warning: unused variable 'pp' [-Wunused-variable]
59 | int hash=0,pp;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14672 KB |
Output is correct |
2 |
Correct |
3 ms |
14724 KB |
Output is correct |
3 |
Correct |
3 ms |
14672 KB |
Output is correct |
4 |
Correct |
4 ms |
14672 KB |
Output is correct |
5 |
Correct |
3 ms |
12796 KB |
Output is correct |
6 |
Correct |
3 ms |
14692 KB |
Output is correct |
7 |
Correct |
3 ms |
14672 KB |
Output is correct |
8 |
Correct |
3 ms |
14672 KB |
Output is correct |
9 |
Correct |
4 ms |
14672 KB |
Output is correct |
10 |
Correct |
3 ms |
14672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
21840 KB |
Output is correct |
2 |
Correct |
50 ms |
21840 KB |
Output is correct |
3 |
Correct |
175 ms |
27568 KB |
Output is correct |
4 |
Correct |
62 ms |
23060 KB |
Output is correct |
5 |
Correct |
56 ms |
20940 KB |
Output is correct |
6 |
Incorrect |
110 ms |
25612 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
14672 KB |
Output is correct |
2 |
Correct |
3 ms |
14724 KB |
Output is correct |
3 |
Correct |
3 ms |
14672 KB |
Output is correct |
4 |
Correct |
4 ms |
14672 KB |
Output is correct |
5 |
Correct |
3 ms |
12796 KB |
Output is correct |
6 |
Correct |
3 ms |
14692 KB |
Output is correct |
7 |
Correct |
3 ms |
14672 KB |
Output is correct |
8 |
Correct |
3 ms |
14672 KB |
Output is correct |
9 |
Correct |
4 ms |
14672 KB |
Output is correct |
10 |
Correct |
3 ms |
14672 KB |
Output is correct |
11 |
Correct |
57 ms |
21840 KB |
Output is correct |
12 |
Correct |
50 ms |
21840 KB |
Output is correct |
13 |
Correct |
175 ms |
27568 KB |
Output is correct |
14 |
Correct |
62 ms |
23060 KB |
Output is correct |
15 |
Correct |
56 ms |
20940 KB |
Output is correct |
16 |
Incorrect |
110 ms |
25612 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14672 KB |
Output is correct |
2 |
Incorrect |
137 ms |
16720 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |