oj.uz

답안 #473658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473658 2021-09-15T19:43:50 Z Sarah_Mokhtar Paths (BOI18_paths) C++14
53 / 100
 274 ms 159332 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define read freopen("acpc.in","r",stdin);
#define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N=1e5+10,M=505,OO=1e16,mod=1e9+9;
int n,m,k,col[N];
vector<int>adj[N];
ll dp[N][1<<6][3];
ll solve(int src,int msk,int cnt){
    ll& ret=dp[src][msk][cnt];
    if(~ret) return ret;
    ret=(cnt==2);
    for(int i:adj[src]){
        if(msk&(1ll<<col[i])) continue;
        ret+=solve(i,msk|(1ll<<col[i]),cnt+(cnt==1));
    }
    return ret;

}
int main(){
    memset(dp,-1,sizeof dp);
    cin>>n>>m>>k;
    for(int i=0;i<n;++i) cin>>col[i];
    while(m--){
        int u,v; cin>>u>>v;
        --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        
    }
    ll ans=0;
    for(int i=0;i<n;++i){
        ans+=solve(i,1<<col[i],1);
    }
    cout<<ans<<'\n';

}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 152952 KB Output is correct
2 Correct 72 ms 152904 KB Output is correct
3 Correct 73 ms 152940 KB Output is correct
4 Correct 71 ms 152836 KB Output is correct
5 Correct 72 ms 152936 KB Output is correct
6 Correct 72 ms 152880 KB Output is correct
7 Correct 73 ms 152916 KB Output is correct
8 Correct 72 ms 152904 KB Output is correct
9 Correct 71 ms 152940 KB Output is correct
10 Correct 72 ms 152920 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 159332 KB Output is correct
2 Correct 240 ms 158776 KB Output is correct
3 Incorrect 89 ms 153576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 152952 KB Output is correct
2 Correct 72 ms 152904 KB Output is correct
3 Correct 73 ms 152940 KB Output is correct
4 Correct 71 ms 152836 KB Output is correct
5 Correct 72 ms 152936 KB Output is correct
6 Correct 72 ms 152880 KB Output is correct
7 Correct 73 ms 152916 KB Output is correct
8 Correct 72 ms 152904 KB Output is correct
9 Correct 71 ms 152940 KB Output is correct
10 Correct 72 ms 152920 KB Output is correct
11 Correct 274 ms 159332 KB Output is correct
12 Correct 240 ms 158776 KB Output is correct
13 Incorrect 89 ms 153576 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 152948 KB Output is correct
2 Correct 152 ms 154776 KB Output is correct
3 Correct 130 ms 154808 KB Output is correct
4 Correct 208 ms 157384 KB Output is correct
5 Correct 192 ms 158128 KB Output is correct
6 Correct 272 ms 157356 KB Output is correct
7 Correct 142 ms 154692 KB Output is correct
8 Correct 242 ms 157400 KB Output is correct
9 Correct 201 ms 158128 KB Output is correct
10 Correct 223 ms 158324 KB Output is correct
11 Correct 232 ms 156100 KB Output is correct
12 Correct 212 ms 157320 KB Output is correct
13 Correct 219 ms 156288 KB Output is correct
14 Correct 249 ms 157376 KB Output is correct
15 Correct 226 ms 157552 KB Output is correct
16 Correct 72 ms 153028 KB Output is correct
17 Correct 71 ms 152884 KB Output is correct
18 Correct 72 ms 152836 KB Output is correct
19 Correct 72 ms 152936 KB Output is correct
20 Correct 71 ms 152852 KB Output is correct
21 Correct 72 ms 152988 KB Output is correct
22 Correct 72 ms 152900 KB Output is correct
23 Correct 72 ms 152920 KB Output is correct
24 Correct 73 ms 152900 KB Output is correct
25 Correct 71 ms 152900 KB Output is correct