oj.uz

Submission #108090

# Submission time Handle Problem Language Result Execution time Memory
108090 2019-04-27T09:19:43 Z Abelyan Paths (BOI18_paths) C++17
100 / 100
 731 ms 170304 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v),v.end()))
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x);
#define dbgv(v);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
#ifdef ALEXPC
#define dbg(x); cout<<#x<<" = "<<x<<endl
#define dbgv(v); cout<<#v<<" = ["; trav(tv,v)cout<<"tv,";cout<<"]"<<endl
#endif

const int N=3*1e5+6;
const ll MOD=1000*1000*1000+7;

int f[N];
ll dp[N][65];
vector<int> g[N];

void rec(int v,int mask){
    if (dp[v][mask]!=0)return;
    dp[v][mask]=1;
    trav(to,g[v]){
        if (f[to]&mask)continue;
        rec(to,mask+f[to]);
        dp[v][mask]+=dp[to][mask+f[to]];
        //cout<<v<<" "<<mask<<" "<<dp[to][ma]
    }

}

int main(){
    fastio;
    srng;
    int n, m, k;
	cin >> n >> m >> k;
	FOR(i, n) {
		cin >> f[i+1];
		f[i+1]--;
		f[i+1]=(1<<f[i+1]);
		//FOR(j,31)dp[i+1][j]=-1;
	}
	FOR(i, m) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
    ll ans=0;
    FORT(i,1,n){
        rec(i,f[i]);
        ans+=dp[i][f[i]];
        ans--;
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7296 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 9 ms 7356 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 13552 KB Output is correct
2 Correct 89 ms 11484 KB Output is correct
3 Correct 633 ms 169704 KB Output is correct
4 Correct 196 ms 27256 KB Output is correct
5 Correct 175 ms 27256 KB Output is correct
6 Correct 438 ms 117156 KB Output is correct
7 Correct 620 ms 169720 KB Output is correct
8 Correct 640 ms 170240 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7296 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 6 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 9 ms 7356 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 126 ms 13552 KB Output is correct
12 Correct 89 ms 11484 KB Output is correct
13 Correct 633 ms 169704 KB Output is correct
14 Correct 196 ms 27256 KB Output is correct
15 Correct 175 ms 27256 KB Output is correct
16 Correct 438 ms 117156 KB Output is correct
17 Correct 620 ms 169720 KB Output is correct
18 Correct 640 ms 170240 KB Output is correct
19 Correct 103 ms 13660 KB Output is correct
20 Correct 85 ms 11260 KB Output is correct
21 Correct 649 ms 169892 KB Output is correct
22 Correct 237 ms 27256 KB Output is correct
23 Correct 162 ms 27256 KB Output is correct
24 Correct 410 ms 117220 KB Output is correct
25 Correct 563 ms 169720 KB Output is correct
26 Correct 560 ms 170304 KB Output is correct
27 Correct 83 ms 11256 KB Output is correct
28 Correct 155 ms 15920 KB Output is correct
29 Correct 731 ms 169780 KB Output is correct
30 Correct 473 ms 90128 KB Output is correct
31 Correct 468 ms 90224 KB Output is correct
32 Correct 683 ms 169712 KB Output is correct
33 Correct 8 ms 7424 KB Output is correct
34 Correct 8 ms 7424 KB Output is correct
35 Correct 8 ms 7424 KB Output is correct
36 Correct 8 ms 7424 KB Output is correct
37 Correct 8 ms 7552 KB Output is correct
38 Correct 8 ms 7424 KB Output is correct
39 Correct 8 ms 7424 KB Output is correct
40 Correct 9 ms 7424 KB Output is correct
41 Correct 9 ms 7424 KB Output is correct
42 Correct 11 ms 7424 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 50 ms 8696 KB Output is correct
3 Correct 29 ms 8704 KB Output is correct
4 Correct 155 ms 61432 KB Output is correct
5 Correct 130 ms 62300 KB Output is correct
6 Correct 227 ms 61560 KB Output is correct
7 Correct 49 ms 8824 KB Output is correct
8 Correct 200 ms 61432 KB Output is correct
9 Correct 141 ms 62244 KB Output is correct
10 Correct 224 ms 62064 KB Output is correct
11 Correct 233 ms 34856 KB Output is correct
12 Correct 171 ms 48752 KB Output is correct
13 Correct 179 ms 34888 KB Output is correct
14 Correct 260 ms 61584 KB Output is correct
15 Correct 221 ms 61560 KB Output is correct
16 Correct 10 ms 7424 KB Output is correct
17 Correct 10 ms 7424 KB Output is correct
18 Correct 9 ms 7424 KB Output is correct
19 Correct 11 ms 7424 KB Output is correct
20 Correct 9 ms 7424 KB Output is correct
21 Correct 9 ms 7424 KB Output is correct
22 Correct 9 ms 7424 KB Output is correct
23 Correct 9 ms 7424 KB Output is correct
24 Correct 10 ms 7424 KB Output is correct
25 Correct 10 ms 7392 KB Output is correct