Submission #730937

#	Time	Username	Problem	Language	Result	Execution time	Memory
730937		Karpin	Paths (BOI18_paths)	C++17	73 / 100	3081 ms	257560 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]--;
        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; 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; 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 / 23
• Subtask 2: 20 / 20
• Subtask 3: 0 / 27
• Subtask 4: 30 / 30