oj.uz

Submission #1116825

# Submission time Handle Problem Language Result Execution time Memory
1116825 2024-11-22T12:42:51 Z 0pt1mus23 Paths (BOI18_paths) C++14
23 / 100
 3000 ms 29616 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;
vector<int> graph[sze];
map<vector<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);
    }
    // for(auto v:ad) cout<<v<<" ";cout<<endl;
    do{
        ord.clear();
        ord.pb(ad[0]);
        for(int i =1;i<k;i++){
            ord.pb(ad[i]);
            if(!var[ord]){
                // 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[ord]=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 3 ms 12112 KB Output is correct
3 Correct 3 ms 12112 KB Output is correct
4 Correct 3 ms 12112 KB Output is correct
5 Correct 3 ms 10064 KB Output is correct
6 Correct 4 ms 12284 KB Output is correct
7 Correct 4 ms 12112 KB Output is correct
8 Correct 3 ms 12112 KB Output is correct
9 Correct 3 ms 12112 KB Output is correct
10 Correct 4 ms 12112 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 22352 KB Output is correct
2 Correct 1473 ms 21692 KB Output is correct
3 Correct 197 ms 29616 KB Output is correct
4 Correct 72 ms 23828 KB Output is correct
5 Correct 64 ms 21892 KB Output is correct
6 Execution timed out 3039 ms 27316 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 3 ms 12112 KB Output is correct
3 Correct 3 ms 12112 KB Output is correct
4 Correct 3 ms 12112 KB Output is correct
5 Correct 3 ms 10064 KB Output is correct
6 Correct 4 ms 12284 KB Output is correct
7 Correct 4 ms 12112 KB Output is correct
8 Correct 3 ms 12112 KB Output is correct
9 Correct 3 ms 12112 KB Output is correct
10 Correct 4 ms 12112 KB Output is correct
11 Correct 320 ms 22352 KB Output is correct
12 Correct 1473 ms 21692 KB Output is correct
13 Correct 197 ms 29616 KB Output is correct
14 Correct 72 ms 23828 KB Output is correct
15 Correct 64 ms 21892 KB Output is correct
16 Execution timed out 3039 ms 27316 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 12368 KB Output is correct
2 Execution timed out 3094 ms 15152 KB Time limit exceeded
3 Halted 0 ms 0 KB -