oj.uz

답안 #210837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210837 2020-03-18T19:22:57 Z bash Paths (BOI18_paths) C++17
0 / 100
 660 ms 311016 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;
}                
#define int ll
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();
    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
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 297852 KB Output is correct
2 Correct 223 ms 297848 KB Output is correct
3 Correct 216 ms 297828 KB Output is correct
4 Correct 200 ms 297888 KB Output is correct
5 Incorrect 217 ms 297948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 305116 KB Output is correct
2 Correct 274 ms 304820 KB Output is correct
3 Correct 660 ms 311016 KB Output is correct
4 Correct 317 ms 306212 KB Output is correct
5 Incorrect 310 ms 306168 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 297852 KB Output is correct
2 Correct 223 ms 297848 KB Output is correct
3 Correct 216 ms 297828 KB Output is correct
4 Correct 200 ms 297888 KB Output is correct
5 Incorrect 217 ms 297948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 297812 KB Output is correct
2 Correct 259 ms 300040 KB Output is correct
3 Correct 221 ms 300596 KB Output is correct
4 Correct 296 ms 303704 KB Output is correct
5 Correct 264 ms 304000 KB Output is correct
6 Correct 369 ms 303508 KB Output is correct
7 Correct 225 ms 300664 KB Output is correct
8 Correct 329 ms 303508 KB Output is correct
9 Correct 293 ms 303916 KB Output is correct
10 Correct 328 ms 304084 KB Output is correct
11 Correct 333 ms 301880 KB Output is correct
12 Correct 291 ms 303036 KB Output is correct
13 Correct 326 ms 302308 KB Output is correct
14 Correct 381 ms 303572 KB Output is correct
15 Correct 347 ms 303608 KB Output is correct
16 Correct 207 ms 297780 KB Output is correct
17 Correct 198 ms 297856 KB Output is correct
18 Correct 203 ms 297876 KB Output is correct
19 Correct 205 ms 297720 KB Output is correct
20 Incorrect 196 ms 297724 KB Output isn't correct
21 Halted 0 ms 0 KB -