oj.uz

Submission #433015

# Submission time Handle Problem Language Result Execution time Memory
433015 2021-06-18T17:45:02 Z Return_0 Paths (BOI18_paths) C++17
100 / 100
 622 ms 100416 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 3e5 + 7, K = 5;

ll c [N], dp [N][1 << K], n, m, k, ans;
vector <ll> adj [N];

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> m >> k;
	for (ll i = 1; i <= n; i++) cin>> c[i], c[i]--, dp[i][1 << c[i]] = 1;
	for (ll v, u; m--;) {
		cin>> v >> u;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	for (ll msk = 1; msk < 1 << k; msk++) for (ll v = 1; v <= n; v++) if (msk >> c[v] & 1) for (auto &u : adj[v])
		dp[v][msk] += dp[u][msk ^ (1 << c[v])];
	for (ll v = 1; v <= n; v++) for (ll msk = 0; msk < 1 << k; msk++) ans += dp[v][msk];
	kill(ans - n);

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
4 3 3
1 2 1 3
1 2
2 3
4 2

9 11 4
1 2 3 4 1 2 1 2 2
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8

*/

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 6 ms 7348 KB Output is correct
4 Correct 6 ms 7396 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 7 ms 7368 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7364 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 18620 KB Output is correct
2 Correct 72 ms 16876 KB Output is correct
3 Correct 458 ms 99780 KB Output is correct
4 Correct 152 ms 26620 KB Output is correct
5 Correct 148 ms 26640 KB Output is correct
6 Correct 329 ms 71992 KB Output is correct
7 Correct 449 ms 99856 KB Output is correct
8 Correct 473 ms 100416 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 6 ms 7372 KB Output is correct
3 Correct 6 ms 7348 KB Output is correct
4 Correct 6 ms 7396 KB Output is correct
5 Correct 6 ms 7372 KB Output is correct
6 Correct 7 ms 7368 KB Output is correct
7 Correct 6 ms 7372 KB Output is correct
8 Correct 6 ms 7364 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 96 ms 18620 KB Output is correct
12 Correct 72 ms 16876 KB Output is correct
13 Correct 458 ms 99780 KB Output is correct
14 Correct 152 ms 26620 KB Output is correct
15 Correct 148 ms 26640 KB Output is correct
16 Correct 329 ms 71992 KB Output is correct
17 Correct 449 ms 99856 KB Output is correct
18 Correct 473 ms 100416 KB Output is correct
19 Correct 92 ms 18580 KB Output is correct
20 Correct 73 ms 16896 KB Output is correct
21 Correct 441 ms 99844 KB Output is correct
22 Correct 166 ms 26520 KB Output is correct
23 Correct 143 ms 26512 KB Output is correct
24 Correct 306 ms 72060 KB Output is correct
25 Correct 446 ms 99852 KB Output is correct
26 Correct 457 ms 100416 KB Output is correct
27 Correct 92 ms 16932 KB Output is correct
28 Correct 106 ms 20812 KB Output is correct
29 Correct 601 ms 99852 KB Output is correct
30 Correct 380 ms 59000 KB Output is correct
31 Correct 424 ms 58968 KB Output is correct
32 Correct 622 ms 99928 KB Output is correct
33 Correct 6 ms 7372 KB Output is correct
34 Correct 7 ms 7372 KB Output is correct
35 Correct 5 ms 7372 KB Output is correct
36 Correct 5 ms 7368 KB Output is correct
37 Correct 6 ms 7372 KB Output is correct
38 Correct 6 ms 7372 KB Output is correct
39 Correct 6 ms 7372 KB Output is correct
40 Correct 6 ms 7372 KB Output is correct
41 Correct 6 ms 7372 KB Output is correct
42 Correct 6 ms 7372 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 30 ms 10320 KB Output is correct
3 Correct 29 ms 10436 KB Output is correct
4 Correct 130 ms 37984 KB Output is correct
5 Correct 97 ms 38480 KB Output is correct
6 Correct 273 ms 38116 KB Output is correct
7 Correct 28 ms 10316 KB Output is correct
8 Correct 160 ms 37964 KB Output is correct
9 Correct 116 ms 38456 KB Output is correct
10 Correct 150 ms 38624 KB Output is correct
11 Correct 158 ms 24064 KB Output is correct
12 Correct 137 ms 31196 KB Output is correct
13 Correct 137 ms 24340 KB Output is correct
14 Correct 274 ms 38060 KB Output is correct
15 Correct 267 ms 38128 KB Output is correct
16 Correct 7 ms 7308 KB Output is correct
17 Correct 6 ms 7372 KB Output is correct
18 Correct 6 ms 7372 KB Output is correct
19 Correct 6 ms 7312 KB Output is correct
20 Correct 7 ms 7372 KB Output is correct
21 Correct 6 ms 7364 KB Output is correct
22 Correct 6 ms 7372 KB Output is correct
23 Correct 6 ms 7372 KB Output is correct
24 Correct 6 ms 7372 KB Output is correct
25 Correct 6 ms 7372 KB Output is correct