oj.uz

답안 #1116829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1116829 2024-11-22T12:54:43 Z 0pt1mus23 Paths (BOI18_paths) C++14
23 / 100
 175 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;
    }
    for(auto v:graph[node]){
        if(col[v]==ord[idx+1]){
            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;
                    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:59:9: warning: unused variable 'hash' [-Wunused-variable]
   59 |     int hash=0,pp;
      |         ^~~~
paths.cpp:59:16: warning: unused variable 'pp' [-Wunused-variable]
   59 |     int hash=0,pp;
      |                ^~

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 3 ms 14724 KB Output is correct
3 Correct 3 ms 14672 KB Output is correct
4 Correct 4 ms 14672 KB Output is correct
5 Correct 3 ms 12796 KB Output is correct
6 Correct 3 ms 14692 KB Output is correct
7 Correct 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 4 ms 14672 KB Output is correct
10 Correct 3 ms 14672 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 21840 KB Output is correct
2 Correct 50 ms 21840 KB Output is correct
3 Correct 175 ms 27568 KB Output is correct
4 Correct 62 ms 23060 KB Output is correct
5 Correct 56 ms 20940 KB Output is correct
6 Incorrect 110 ms 25612 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 3 ms 14724 KB Output is correct
3 Correct 3 ms 14672 KB Output is correct
4 Correct 4 ms 14672 KB Output is correct
5 Correct 3 ms 12796 KB Output is correct
6 Correct 3 ms 14692 KB Output is correct
7 Correct 3 ms 14672 KB Output is correct
8 Correct 3 ms 14672 KB Output is correct
9 Correct 4 ms 14672 KB Output is correct
10 Correct 3 ms 14672 KB Output is correct
11 Correct 57 ms 21840 KB Output is correct
12 Correct 50 ms 21840 KB Output is correct
13 Correct 175 ms 27568 KB Output is correct
14 Correct 62 ms 23060 KB Output is correct
15 Correct 56 ms 20940 KB Output is correct
16 Incorrect 110 ms 25612 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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