oj.uz

Submission #1116826

# Submission time Handle Problem Language Result Execution time Memory
1116826 2024-11-22T12:45:27 Z 0pt1mus23 Paths (BOI18_paths) C++14
23 / 100
 3000 ms 25096 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];
map<int,int> var;
vector<int> ord;
int col[sze];
int dp[sze];
int nxt[sze];

void dfs(int node,int idx){
    if(idx== (ord.size()-1 ) ){
        dp[node]=1;
        return;
    }
    for(auto v:graph[node]){
        if(col[v]==ord[idx+1]){
            dp[v]=0;
            dfs(v,idx+1);
            dp[node]+=dp[v];
        }
    }
}
vector<int> cc[10];

void fast(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i =1;i<=n;i++){
        cin>>col[i];
        cc[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{
        hash=ad[0],pp=1;
        ord.clear();
        ord.pb(ad[0]);
        for(int i =1;i<k;i++){
            pp = (pp* pr)%mod;
            hash=(hash + ad[i] * pp  % mod) %mod;
            ord.pb(ad[i]);
            if(!var[hash]){
                // for(auto v:ord) cout<<v<<" ,";cout<<endl;
                for(int j=1;j<=n;j++){
                    dp[j]=0;    
                }
                for(auto v:cc[ord[0]]){

                    dfs(v,0);
                    if(dp[v]){
                        // cout<<v<<" == "<<dp[v]<<endl;
                        ans=(ans+dp[v])%mod;
                    }
                }
                var[hash]=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:22: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]
   22 |     if(idx== (ord.size()-1 ) ){
      |        ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12112 KB Output is correct
2 Correct 4 ms 12112 KB Output is correct
3 Correct 4 ms 12112 KB Output is correct
4 Correct 4 ms 12112 KB Output is correct
5 Correct 4 ms 10064 KB Output is correct
6 Correct 3 ms 12216 KB Output is correct
7 Correct 4 ms 12284 KB Output is correct
8 Correct 3 ms 12112 KB Output is correct
9 Correct 3 ms 12112 KB Output is correct
10 Correct 5 ms 12112 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 19344 KB Output is correct
2 Correct 1478 ms 19236 KB Output is correct
3 Correct 153 ms 25096 KB Output is correct
4 Correct 60 ms 20500 KB Output is correct
5 Correct 53 ms 18504 KB Output is correct
6 Execution timed out 3065 ms 23052 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12112 KB Output is correct
2 Correct 4 ms 12112 KB Output is correct
3 Correct 4 ms 12112 KB Output is correct
4 Correct 4 ms 12112 KB Output is correct
5 Correct 4 ms 10064 KB Output is correct
6 Correct 3 ms 12216 KB Output is correct
7 Correct 4 ms 12284 KB Output is correct
8 Correct 3 ms 12112 KB Output is correct
9 Correct 3 ms 12112 KB Output is correct
10 Correct 5 ms 12112 KB Output is correct
11 Correct 308 ms 19344 KB Output is correct
12 Correct 1478 ms 19236 KB Output is correct
13 Correct 153 ms 25096 KB Output is correct
14 Correct 60 ms 20500 KB Output is correct
15 Correct 53 ms 18504 KB Output is correct
16 Execution timed out 3065 ms 23052 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12112 KB Output is correct
2 Execution timed out 3080 ms 14416 KB Time limit exceeded
3 Halted 0 ms 0 KB -