제출 #730916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
730916		Karpin	Paths (BOI18_paths)	C++17	23 / 100	3076 ms	242760 KiB

paths

#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 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30