oj.uz

Submission #730914

# Submission time Handle Problem Language Result Execution time Memory
730914 2023-04-26T15:37:16 Z Karpin Paths (BOI18_paths) C++17
23 / 100
 3000 ms 251388 KB 
#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define vt vector
#define ar array


void solve(){
		
    int n, m, k;
    cin >> n >> m >> k;

    int colors[n];

    for(int i = 0; i < n; i++){
        cin >> colors[i];
        colors[i]--;
    }

    map<int, vt<int>> lines;

    vt<pair<int, int>> onlyLines;

    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (lines.find(a) == lines.end()) lines[a] = {};
        if (lines.find(b) == lines.end()) lines[b] = {};

        lines[a].push_back(b);
        lines[b].push_back(a);
        onlyLines.push_back({a, b});
    }


    map<int, map<int, int>> amount;


    for(int i = 0; i < n; i++){
        amount[i] = {};
        for(int j = 0; j < 1<<k; j++){
            if (__builtin_popcount(j) == 1){
                if (j & (int) (pow(2, colors[i]))) amount[i][j] = 1;
                else amount[i][j] = 0;
            }else amount[i][j] = 0;
        }
    }

    ll res = 0;


    for(int i = 2; i <= k; i++){
        for (pair<int, int> line : onlyLines){
            for(int j = 0; j < 1<<(k + 1); j++){
                if (__builtin_popcount(j) == i){
                    if (j & (int) pow(2, colors[line.first])) {
                        ll mykk = amount[line.second][j - pow(2, colors[line.first])];
                        amount[line.first][j] += mykk;
                        res += mykk;
                    }
                    if (j & (int) pow(2, colors[line.second])) {
                        ll mykk = amount[line.first][j - pow(2, colors[line.second])];
                        amount[line.second][j] += mykk;
                        res += mykk;
                    }
                }
            }
        }
    }

    cout << res << endl;


}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int testcases = 1;

	// cin >> testcases;

	while(testcases--){
		solve();
	}

	return 0;

}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1191 ms 12904 KB Output is correct
2 Correct 844 ms 10248 KB Output is correct
3 Execution timed out 3055 ms 229344 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1191 ms 12904 KB Output is correct
12 Correct 844 ms 10248 KB Output is correct
13 Execution timed out 3055 ms 229344 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1343 ms 4252 KB Output is correct
3 Correct 263 ms 3276 KB Output is correct
4 Correct 1040 ms 82548 KB Output is correct
5 Correct 784 ms 86228 KB Output is correct
6 Execution timed out 3075 ms 251388 KB Time limit exceeded
7 Halted 0 ms 0 KB -