oj.uz

Submission #1116827

# Submission time Handle Problem Language Result Execution time Memory
1116827 2024-11-22T12:49:32 Z 0pt1mus23 Paths (BOI18_paths) C++14
23 / 100
 3000 ms 25208 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 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(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> 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;    
                }
                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: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 ) ){
      |        ~~~^~~~~~~~~~~~~~~~~~
paths.cpp: In function 'void fast()':
paths.cpp:55:9: warning: unused variable 'hash' [-Wunused-variable]
   55 |     int hash=0,pp;
      |         ^~~~
paths.cpp:55:16: warning: unused variable 'pp' [-Wunused-variable]
   55 |     int hash=0,pp;
      |                ^~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12368 KB Output is correct
2 Correct 3 ms 12260 KB Output is correct
3 Correct 3 ms 12184 KB Output is correct
4 Correct 3 ms 12368 KB Output is correct
5 Correct 3 ms 10320 KB Output is correct
6 Correct 3 ms 12368 KB Output is correct
7 Correct 3 ms 12368 KB Output is correct
8 Correct 3 ms 12368 KB Output is correct
9 Correct 3 ms 12368 KB Output is correct
10 Correct 3 ms 12536 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 19624 KB Output is correct
2 Correct 1531 ms 19280 KB Output is correct
3 Correct 175 ms 25208 KB Output is correct
4 Correct 62 ms 20692 KB Output is correct
5 Correct 54 ms 18644 KB Output is correct
6 Execution timed out 3062 ms 23328 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12368 KB Output is correct
2 Correct 3 ms 12260 KB Output is correct
3 Correct 3 ms 12184 KB Output is correct
4 Correct 3 ms 12368 KB Output is correct
5 Correct 3 ms 10320 KB Output is correct
6 Correct 3 ms 12368 KB Output is correct
7 Correct 3 ms 12368 KB Output is correct
8 Correct 3 ms 12368 KB Output is correct
9 Correct 3 ms 12368 KB Output is correct
10 Correct 3 ms 12536 KB Output is correct
11 Correct 305 ms 19624 KB Output is correct
12 Correct 1531 ms 19280 KB Output is correct
13 Correct 175 ms 25208 KB Output is correct
14 Correct 62 ms 20692 KB Output is correct
15 Correct 54 ms 18644 KB Output is correct
16 Execution timed out 3062 ms 23328 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 3071 ms 14592 KB Time limit exceeded
3 Halted 0 ms 0 KB -