oj.uz

답안 #151148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
151148 2019-09-01T21:39:05 Z Blagojce Paths (BOI18_paths) C++11
23 / 100
 3000 ms 13872 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;

int n, m, k;
int col[300005];
vector<int> g[300005];

void input(){
        cin >> n >> m >> k;
        fr(i, 0, n){
                cin >> col[i];
                --col[i];
        }
        fr(i, 0, m){
                int a, b;
                cin >> a >> b;
                --a,--b;
                g[a].pb(b);
                g[b].pb(a);
        }
}
ll dfs(int u, int bit){
        ll cnt = 0;
        for(auto e : g[u]){
                if((bit&(1 << col[e])) == 0){
                        cnt += dfs(e,(bit|(1<<col[e]))) + 1;
                }
        }
        return cnt;
}
void solve(){
        ll ANS = 0;
        fr(i, 0, n){
                ANS += dfs(i, (1 << col[i]));
        }
        cout << ANS << endl;
}


int main()
{
        input();
        solve();
        return 0;
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7420 KB Output is correct
3 Correct 8 ms 7288 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 8 ms 7288 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2933 ms 13872 KB Output is correct
2 Execution timed out 3043 ms 13176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7420 KB Output is correct
3 Correct 8 ms 7288 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 8 ms 7288 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 2933 ms 13872 KB Output is correct
12 Execution timed out 3043 ms 13176 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Execution timed out 3033 ms 9080 KB Time limit exceeded
3 Halted 0 ms 0 KB -