답안 #108090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108090	2019-04-27T09:19:43 Z	Abelyan	Paths (BOI18_paths)	C++17	100 / 100	731 ms	170304 KB

paths

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #108090

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 20.0 / 20.0

Subtask #3 27.0 / 27.0

Subtask #4 30.0 / 30.0

Subtask #1
23.0 / 23.0

Subtask #2
20.0 / 20.0

Subtask #3
27.0 / 27.0

Subtask #4
30.0 / 30.0