oj.uz

Submission #363462

# Submission time Handle Problem Language Result Execution time Memory
363462 2021-02-06T07:12:04 Z knightron0 Paths (BOI18_paths) C++14
53 / 100
 285 ms 35948 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e5 + 5;

vector<int> adj[MAXN];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    int n, m, k;
    cin>>n>>m>>k;
    int col[n+4];
    for(int i= 1;i<=n;i++){
    	cin>>col[i];
    	col[i]--;
    }
    for(int i= 0;i<m;i++){
    	int t1, t2;
    	cin>>t1>>t2;
    	adj[t1].pb(t2);
    	adj[t2].pb(t1);
    }
    int dp[n+3][(1<<k)+3];
    clr(dp, 0);
    for(int i= 1;i<=n;i++){
    	dp[i][(1<<col[i])] = 1;
    }
    int ans= 0;
   	for(int mask = 0;mask<(1<<k);mask++){
   		for(int i= 1;i<=n;i++){
   			if((1<<col[i])&mask){
   				for(int v: adj[i]){
   					int newmask = (1<<col[v]) | mask;
   					if((1<<col[v]) & mask) continue;
   					dp[v][newmask] += dp[i][mask];
   					if(__builtin_popcount(newmask)>1){
   						ans += dp[i][mask];
   					}
   				}
   			}
   		}
   	}

   	cout<<ans<<endl;
    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 13164 KB Output is correct
2 Correct 96 ms 12140 KB Output is correct
3 Runtime error 35 ms 10732 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct
11 Correct 107 ms 13164 KB Output is correct
12 Correct 96 ms 12140 KB Output is correct
13 Runtime error 35 ms 10732 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 45 ms 5740 KB Output is correct
3 Correct 27 ms 5868 KB Output is correct
4 Correct 113 ms 17136 KB Output is correct
5 Correct 81 ms 17376 KB Output is correct
6 Correct 285 ms 35948 KB Output is correct
7 Correct 33 ms 5740 KB Output is correct
8 Correct 200 ms 23148 KB Output is correct
9 Correct 124 ms 23648 KB Output is correct
10 Correct 160 ms 23392 KB Output is correct
11 Correct 163 ms 20580 KB Output is correct
12 Correct 184 ms 28252 KB Output is correct
13 Correct 153 ms 20700 KB Output is correct
14 Correct 277 ms 35948 KB Output is correct
15 Correct 280 ms 35948 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 2 ms 2668 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 2 ms 2796 KB Output is correct
22 Correct 2 ms 2668 KB Output is correct
23 Correct 3 ms 2668 KB Output is correct
24 Correct 3 ms 2668 KB Output is correct
25 Correct 2 ms 2688 KB Output is correct