Submission #730958

#	Time	Username	Problem	Language	Result	Execution time	Memory
730958		Karpin	Paths (BOI18_paths)	C++17	100 / 100	2945 ms	271956 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];

    map<pair<int, int>, vt<int>> remaining;

    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;
    int myypow = pow(2, k) - 1;

    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);
        if (colors[a] == colors[b]) continue;
        onlyLines.push_back({a, b});
        remaining[{a, b}] = {};
        for(int kkk = 1; kkk < myypow + 1; kkk *= 2){
            if (colors[a] == kkk || colors[b] == kkk) continue;
            remaining[{a, b}].push_back(kkk);
        }
    }

    vt<pair<int, int>> kra = {{0, 1}, {0, 2}, {1, 2}};


    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++){
        for (pair<int, int> line : onlyLines){
            
            int j = colors[line.first] + colors[line.second];
            if (i == 2){
                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;
            }
            else if (i == 3){
                for(int kl = 0; kl < k - 2; kl++){
                    j += remaining[line][kl];
                    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;
                    j -= remaining[line][kl];
                }
            }
            if (i == 4 && k == 5){
                
                for(int kl = 0; kl < k - 2; kl++){
                    j += remaining[line][kra[kl].first];
                    j += remaining[line][kra[kl].second];
                    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;
                    j -= remaining[line][kra[kl].first];
                    j -= remaining[line][kra[kl].second];
                }
            }
            if (i == 5 || (i == 4 && k == 4)){
                j = myypow;
                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: 27 / 27
• Subtask 4: 30 / 30