oj.uz

답안 #1116858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1116858 2024-11-22T13:31:46 Z 0pt1mus23 Paths (BOI18_paths) C++14
23 / 100
 162 ms 25032 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(dp[node]!=-1){
        return;
    }
    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)%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]=-1;
                }
                for(auto v:co[ord[0]]){
                    dfs(v,0);
                    if(dp[v]){
                        // cout<<v<<" == "<<dp[v]<<endl;
                        ans=(ans+dp[v] + mod)%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:25: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]
   25 |     if(idx== (ord.size()-1 )){
      |        ~~~^~~~~~~~~~~~~~~~~~
paths.cpp: In function 'void fast()':
paths.cpp:58:9: warning: unused variable 'hash' [-Wunused-variable]
   58 |     int hash=0,pp;
      |         ^~~~
paths.cpp:58:16: warning: unused variable 'pp' [-Wunused-variable]
   58 |     int hash=0,pp;
      |                ^~

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12368 KB Output is correct
2 Correct 3 ms 12368 KB Output is correct
3 Correct 3 ms 12368 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 12380 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 12368 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 19540 KB Output is correct
2 Correct 57 ms 19380 KB Output is correct
3 Correct 162 ms 25032 KB Output is correct
4 Correct 61 ms 20500 KB Output is correct
5 Correct 56 ms 18636 KB Output is correct
6 Incorrect 113 ms 23168 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12368 KB Output is correct
2 Correct 3 ms 12368 KB Output is correct
3 Correct 3 ms 12368 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 12380 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 12368 KB Output is correct
11 Correct 64 ms 19540 KB Output is correct
12 Correct 57 ms 19380 KB Output is correct
13 Correct 162 ms 25032 KB Output is correct
14 Correct 61 ms 20500 KB Output is correct
15 Correct 56 ms 18636 KB Output is correct
16 Incorrect 113 ms 23168 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12536 KB Output is correct
2 Incorrect 138 ms 14416 KB Output isn't correct
3 Halted 0 ms 0 KB -