답안 #108089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108089	2019-04-27T09:17:22 Z	Abelyan	Paths (BOI18_paths)	C++17	100 / 100	737 ms	170332 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];
ull 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);
	}
    ull ans=0;
    FORT(i,1,n){
        rec(i,f[i]);
        ans+=dp[i][f[i]];
    }
    cout<<ans-n<<endl;
    return 0;
}

Subtask #1
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7424 KB	Output is correct
2	Correct	9 ms	7424 KB	Output is correct
3	Correct	8 ms	7424 KB	Output is correct
4	Correct	8 ms	7424 KB	Output is correct
5	Correct	8 ms	7424 KB	Output is correct
6	Correct	8 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	7424 KB	Output is correct
10	Correct	8 ms	7396 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	138 ms	13628 KB	Output is correct
2	Correct	95 ms	11384 KB	Output is correct
3	Correct	589 ms	169576 KB	Output is correct
4	Correct	221 ms	27256 KB	Output is correct
5	Correct	179 ms	27376 KB	Output is correct
6	Correct	392 ms	117096 KB	Output is correct
7	Correct	601 ms	169648 KB	Output is correct
8	Correct	616 ms	170232 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	7424 KB	Output is correct
2	Correct	9 ms	7424 KB	Output is correct
3	Correct	8 ms	7424 KB	Output is correct
4	Correct	8 ms	7424 KB	Output is correct
5	Correct	8 ms	7424 KB	Output is correct
6	Correct	8 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	7424 KB	Output is correct
10	Correct	8 ms	7396 KB	Output is correct
11	Correct	138 ms	13628 KB	Output is correct
12	Correct	95 ms	11384 KB	Output is correct
13	Correct	589 ms	169576 KB	Output is correct
14	Correct	221 ms	27256 KB	Output is correct
15	Correct	179 ms	27376 KB	Output is correct
16	Correct	392 ms	117096 KB	Output is correct
17	Correct	601 ms	169648 KB	Output is correct
18	Correct	616 ms	170232 KB	Output is correct
19	Correct	138 ms	13724 KB	Output is correct
20	Correct	104 ms	11580 KB	Output is correct
21	Correct	647 ms	169592 KB	Output is correct
22	Correct	232 ms	27460 KB	Output is correct
23	Correct	158 ms	27256 KB	Output is correct
24	Correct	409 ms	117096 KB	Output is correct
25	Correct	648 ms	169648 KB	Output is correct
26	Correct	621 ms	170332 KB	Output is correct
27	Correct	97 ms	11384 KB	Output is correct
28	Correct	128 ms	15864 KB	Output is correct
29	Correct	737 ms	169720 KB	Output is correct
30	Correct	468 ms	90292 KB	Output is correct
31	Correct	495 ms	90352 KB	Output is correct
32	Correct	681 ms	169604 KB	Output is correct
33	Correct	9 ms	7424 KB	Output is correct
34	Correct	8 ms	7424 KB	Output is correct
35	Correct	9 ms	7424 KB	Output is correct
36	Correct	11 ms	7424 KB	Output is correct
37	Correct	10 ms	7552 KB	Output is correct
38	Correct	8 ms	7424 KB	Output is correct
39	Correct	10 ms	7424 KB	Output is correct
40	Correct	10 ms	7424 KB	Output is correct
41	Correct	10 ms	7424 KB	Output is correct
42	Correct	9 ms	7424 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	7424 KB	Output is correct
2	Correct	51 ms	8776 KB	Output is correct
3	Correct	32 ms	9464 KB	Output is correct
4	Correct	153 ms	62848 KB	Output is correct
5	Correct	132 ms	63596 KB	Output is correct
6	Correct	232 ms	62908 KB	Output is correct
7	Correct	35 ms	9464 KB	Output is correct
8	Correct	204 ms	63020 KB	Output is correct
9	Correct	154 ms	63664 KB	Output is correct
10	Correct	189 ms	63472 KB	Output is correct
11	Correct	149 ms	36212 KB	Output is correct
12	Correct	139 ms	49956 KB	Output is correct
13	Correct	167 ms	36036 KB	Output is correct
14	Correct	267 ms	62840 KB	Output is correct
15	Correct	232 ms	62944 KB	Output is correct
16	Correct	9 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	8 ms	7424 KB	Output is correct
20	Correct	10 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	8 ms	7424 KB	Output is correct
24	Correct	9 ms	7424 KB	Output is correct
25	Correct	10 ms	7424 KB	Output is correct

답안 #108089

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