oj.uz

Submission #730927

# Submission time Handle Problem Language Result Execution time Memory
730927 2023-04-26T15:49:24 Z Karpin Paths (BOI18_paths) C++17
23 / 100
 3000 ms 311428 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]--;
        if (colors[i] == 0) colors[i] = 1;
        else if (colors[i] == 1) colors[i] = 2;
        else if (colors[i] == 2) colors[i] = 4;
        else if (colors[i] == 3) colors[i] = 8;
        else if (colors[i] == 4) colors[i] = 16;
    }

    // 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 + 1); j++){
            if (__builtin_popcount(j) == 1){
                if (j & 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 & colors[line.first]) {
                    ll mykk = amount[line.second][j - colors[line.first]];
                    amount[line.first][j] += mykk;
                    res += mykk;
                }
                if (j & colors[line.second]) {
                    ll mykk = amount[line.first][j - 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 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 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 899 ms 6960 KB Output is correct
2 Correct 578 ms 4556 KB Output is correct
3 Execution timed out 3081 ms 257444 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 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 899 ms 6960 KB Output is correct
12 Correct 578 ms 4556 KB Output is correct
13 Execution timed out 3081 ms 257444 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 896 ms 2592 KB Output is correct
3 Correct 176 ms 1508 KB Output is correct
4 Correct 945 ms 86024 KB Output is correct
5 Correct 760 ms 86020 KB Output is correct
6 Execution timed out 3069 ms 311428 KB Time limit exceeded
7 Halted 0 ms 0 KB -