oj.uz

Submission #730939

# Submission time Handle Problem Language Result Execution time Memory
730939 2023-04-26T16:14:32 Z Karpin Paths (BOI18_paths) C++17
73 / 100
 3000 ms 243364 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;

    amount[0] = {};

    for(int j = 1; j < 1<<k; j++){
        amount[0][j] = 0;
    }
    for(int i = 1; i < n; i++) amount[i] = amount[0];

    for(int i = 0; i < n; i++){
        amount[i][colors[i]] = 1;
    }

    ll res = 0;


    for(int i = 2; i <= k; i++){
        vt<int> nums = {};
        for(int j = 3; j < 1<<k; 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]) || !(j & colors[line.second])) continue;
                ll mykk = amount[line.second][j - colors[line.first]];
                amount[line.first][j] += mykk;
                res += mykk;
                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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 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 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 4792 KB Output is correct
2 Correct 243 ms 4488 KB Output is correct
3 Correct 1673 ms 130648 KB Output is correct
4 Correct 306 ms 9856 KB Output is correct
5 Correct 55 ms 6904 KB Output is correct
6 Correct 1107 ms 87988 KB Output is correct
7 Correct 1675 ms 130644 KB Output is correct
8 Correct 1634 ms 130776 KB Output is correct

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 0 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 0 ms 212 KB Output is correct
11 Correct 374 ms 4792 KB Output is correct
12 Correct 243 ms 4488 KB Output is correct
13 Correct 1673 ms 130648 KB Output is correct
14 Correct 306 ms 9856 KB Output is correct
15 Correct 55 ms 6904 KB Output is correct
16 Correct 1107 ms 87988 KB Output is correct
17 Correct 1675 ms 130644 KB Output is correct
18 Correct 1634 ms 130776 KB Output is correct
19 Correct 376 ms 4792 KB Output is correct
20 Correct 257 ms 4532 KB Output is correct
21 Correct 1674 ms 130744 KB Output is correct
22 Correct 271 ms 9816 KB Output is correct
23 Correct 58 ms 6996 KB Output is correct
24 Correct 1104 ms 87984 KB Output is correct
25 Correct 1648 ms 130652 KB Output is correct
26 Correct 1658 ms 130692 KB Output is correct
27 Correct 591 ms 4528 KB Output is correct
28 Correct 898 ms 9076 KB Output is correct
29 Execution timed out 3071 ms 243364 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 325 ms 1844 KB Output is correct
3 Correct 76 ms 1492 KB Output is correct
4 Correct 441 ms 43760 KB Output is correct
5 Correct 320 ms 43716 KB Output is correct
6 Correct 1415 ms 156504 KB Output is correct
7 Correct 160 ms 1484 KB Output is correct
8 Correct 825 ms 81344 KB Output is correct
9 Correct 586 ms 81336 KB Output is correct
10 Correct 680 ms 81328 KB Output is correct
11 Correct 874 ms 78776 KB Output is correct
12 Correct 967 ms 117624 KB Output is correct
13 Correct 903 ms 78760 KB Output is correct
14 Correct 1440 ms 156472 KB Output is correct
15 Correct 1467 ms 156476 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct