oj.uz

Submission #1116831

# Submission time Handle Problem Language Result Execution time Memory
1116831 2024-11-22T12:59:19 Z 0pt1mus23 Paths (BOI18_paths) C++14
23 / 100
 237 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;
    }
    dp[node]=0;
    for(auto v:graph[node]){
        if(col[v]==ord[idx+1]){
            dfs(v,idx+1);
            dp[node]=(dp[node]+ dp[v])%mod;
        }
    }
}
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:60:9: warning: unused variable 'hash' [-Wunused-variable]
   60 |     int hash=0,pp;
      |         ^~~~
paths.cpp:60:16: warning: unused variable 'pp' [-Wunused-variable]
   60 |     int hash=0,pp;
      |                ^~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 4 ms 14672 KB Output is correct
3 Correct 3 ms 14624 KB Output is correct
4 Correct 4 ms 14672 KB Output is correct
5 Correct 3 ms 12624 KB Output is correct
6 Correct 3 ms 14520 KB Output is correct
7 Correct 4 ms 14924 KB Output is correct
8 Correct 5 ms 14672 KB Output is correct
9 Correct 4 ms 14672 KB Output is correct
10 Correct 4 ms 14672 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 21832 KB Output is correct
2 Correct 50 ms 21840 KB Output is correct
3 Correct 237 ms 27568 KB Output is correct
4 Correct 70 ms 23060 KB Output is correct
5 Correct 57 ms 20944 KB Output is correct
6 Incorrect 140 ms 25612 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 4 ms 14672 KB Output is correct
3 Correct 3 ms 14624 KB Output is correct
4 Correct 4 ms 14672 KB Output is correct
5 Correct 3 ms 12624 KB Output is correct
6 Correct 3 ms 14520 KB Output is correct
7 Correct 4 ms 14924 KB Output is correct
8 Correct 5 ms 14672 KB Output is correct
9 Correct 4 ms 14672 KB Output is correct
10 Correct 4 ms 14672 KB Output is correct
11 Correct 66 ms 21832 KB Output is correct
12 Correct 50 ms 21840 KB Output is correct
13 Correct 237 ms 27568 KB Output is correct
14 Correct 70 ms 23060 KB Output is correct
15 Correct 57 ms 20944 KB Output is correct
16 Incorrect 140 ms 25612 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Incorrect 141 ms 16720 KB Output isn't correct
3 Halted 0 ms 0 KB -