oj.uz

답안 #210840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210840 2020-03-18T19:25:07 Z bash Paths (BOI18_paths) C++17
23 / 100
 686 ms 170380 KB 
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
 
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
 using namespace __gnu_pbds;
using namespace std;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;

typedef long long ll;

#define pii pair<int,int>
 
long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}                

int a[MAXN];
int dp[MAXN][(1 << 5) + 3];
int n, m, k;                
vector<int> g[MAXN];

int solve(int v, int mask) {
	if (__builtin_popcount(mask) == k) {
		return 1;		
	}
	if (~dp[v][mask]) return dp[v][mask];
	int &ans  = dp[v][mask];
	ans = 0;
	if (__builtin_popcount(mask) > 1) {
		ans += solve(v, (1 << k) - 1);
	}
	for (int i : g[v]) {
		if ((mask >> a[i]) & 1) continue;
		ans += solve(i, mask | (1 << a[i]));
	}                                       
	return ans;
}

main() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    n = readInt(), m = readInt(), k = readInt();
    if (k == 1) {
    	cout << 0;
    	return 0;
    }
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++) {
    	a[i] = readInt() - 1;
    }
    for (int i = 1; i <= m; i++) {
		int u = readInt(), v = readInt();
		g[v].pb(u);
		g[u].pb(v);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
    	ans += solve(i, (1 << (a[i])));
    }
    cout << ans << endl;
	return 0;
}

Compilation message

paths.cpp:101:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 160840 KB Output is correct
2 Correct 158 ms 160768 KB Output is correct
3 Correct 120 ms 160760 KB Output is correct
4 Correct 126 ms 160800 KB Output is correct
5 Correct 28 ms 23772 KB Output is correct
6 Correct 122 ms 160804 KB Output is correct
7 Correct 125 ms 160752 KB Output is correct
8 Correct 125 ms 160836 KB Output is correct
9 Correct 127 ms 160804 KB Output is correct
10 Correct 144 ms 160732 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 164444 KB Output is correct
2 Correct 188 ms 164348 KB Output is correct
3 Correct 686 ms 170380 KB Output is correct
4 Correct 270 ms 165420 KB Output is correct
5 Correct 22 ms 23828 KB Output is correct
6 Incorrect 490 ms 168752 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 160840 KB Output is correct
2 Correct 158 ms 160768 KB Output is correct
3 Correct 120 ms 160760 KB Output is correct
4 Correct 126 ms 160800 KB Output is correct
5 Correct 28 ms 23772 KB Output is correct
6 Correct 122 ms 160804 KB Output is correct
7 Correct 125 ms 160752 KB Output is correct
8 Correct 125 ms 160836 KB Output is correct
9 Correct 127 ms 160804 KB Output is correct
10 Correct 144 ms 160732 KB Output is correct
11 Correct 241 ms 164444 KB Output is correct
12 Correct 188 ms 164348 KB Output is correct
13 Correct 686 ms 170380 KB Output is correct
14 Correct 270 ms 165420 KB Output is correct
15 Correct 22 ms 23828 KB Output is correct
16 Incorrect 490 ms 168752 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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