oj.uz

Submission #730919

# Submission time Handle Problem Language Result Execution time Memory
730919 2023-04-26T15:41:51 Z Karpin Paths (BOI18_paths) C++17
23 / 100
 3000 ms 243724 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++){
        vt<int> nums = {};
        for(int j = 0; j < 1<<(k + 1); j++){
            if (__builtin_popcount(j) == i) nums.push_back(j);
        }
        for (pair<int, int> line : onlyLines){
            for(int j : nums){
                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 340 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1043 ms 6456 KB Output is correct
2 Correct 749 ms 4548 KB Output is correct
3 Execution timed out 3067 ms 209784 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 340 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1043 ms 6456 KB Output is correct
12 Correct 749 ms 4548 KB Output is correct
13 Execution timed out 3067 ms 209784 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1257 ms 2540 KB Output is correct
3 Correct 260 ms 1504 KB Output is correct
4 Correct 942 ms 71672 KB Output is correct
5 Correct 705 ms 73540 KB Output is correct
6 Execution timed out 3101 ms 243724 KB Time limit exceeded
7 Halted 0 ms 0 KB -