oj.uz

Submission #730932

# Submission time Handle Problem Language Result Execution time Memory
730932 2023-04-26T15:55:36 Z Karpin Paths (BOI18_paths) C++17
73 / 100
 3000 ms 487276 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 = 0; j < 1<<(k + 1); 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 = 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]) || !(j & colors[line.second])) continue;
                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 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 480 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 6908 KB Output is correct
2 Correct 467 ms 4436 KB Output is correct
3 Correct 2612 ms 257452 KB Output is correct
4 Correct 486 ms 20236 KB Output is correct
5 Correct 69 ms 14504 KB Output is correct
6 Correct 1875 ms 176624 KB Output is correct
7 Correct 2578 ms 261948 KB Output is correct
8 Correct 2533 ms 261940 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 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 480 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 757 ms 6908 KB Output is correct
12 Correct 467 ms 4436 KB Output is correct
13 Correct 2612 ms 257452 KB Output is correct
14 Correct 486 ms 20236 KB Output is correct
15 Correct 69 ms 14504 KB Output is correct
16 Correct 1875 ms 176624 KB Output is correct
17 Correct 2578 ms 261948 KB Output is correct
18 Correct 2533 ms 261940 KB Output is correct
19 Correct 659 ms 9724 KB Output is correct
20 Correct 416 ms 6704 KB Output is correct
21 Correct 2563 ms 261940 KB Output is correct
22 Correct 433 ms 20196 KB Output is correct
23 Correct 66 ms 14552 KB Output is correct
24 Correct 1776 ms 176612 KB Output is correct
25 Correct 2590 ms 261944 KB Output is correct
26 Correct 2832 ms 262020 KB Output is correct
27 Correct 953 ms 6612 KB Output is correct
28 Correct 1654 ms 18340 KB Output is correct
29 Execution timed out 3106 ms 487276 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 224 KB Output is correct
2 Correct 640 ms 2720 KB Output is correct
3 Correct 139 ms 1632 KB Output is correct
4 Correct 708 ms 86148 KB Output is correct
5 Correct 501 ms 86244 KB Output is correct
6 Correct 2381 ms 311596 KB Output is correct
7 Correct 309 ms 2652 KB Output is correct
8 Correct 1453 ms 162520 KB Output is correct
9 Correct 986 ms 162540 KB Output is correct
10 Correct 1048 ms 162536 KB Output is correct
11 Correct 1755 ms 157336 KB Output is correct
12 Correct 1434 ms 235076 KB Output is correct
13 Correct 1487 ms 157324 KB Output is correct
14 Correct 2299 ms 312816 KB Output is correct
15 Correct 2411 ms 312820 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 452 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 448 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct