oj.uz

Submission #730916

# Submission time Handle Problem Language Result Execution time Memory
730916 2023-04-26T15:39:27 Z Karpin Paths (BOI18_paths) C++17
23 / 100
 3000 ms 242760 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 6524 KB Output is correct
2 Correct 774 ms 4548 KB Output is correct
3 Execution timed out 3076 ms 210516 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1020 ms 6524 KB Output is correct
12 Correct 774 ms 4548 KB Output is correct
13 Execution timed out 3076 ms 210516 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 1341 ms 2544 KB Output is correct
3 Correct 243 ms 1492 KB Output is correct
4 Correct 975 ms 71764 KB Output is correct
5 Correct 733 ms 73392 KB Output is correct
6 Execution timed out 3053 ms 242760 KB Time limit exceeded
7 Halted 0 ms 0 KB -