Submission #877135

#	Time	Username	Problem	Language	Result	Execution time	Memory
877135		MasterTaster	Paths (BOI18_paths)	C++14	70 / 100	260 ms	25948 KiB

paths

#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 300010
#define MAXK 6

using namespace std;

int n, m, k, a[MAXN];
ll cnt[MAXN][MAXK], ress;
vector<pii> grane;

int main() {
    cin>>n>>m>>k;

    for (int i=1; i<=n; i++)
        cin>>a[i];

    for (int i=0; i<m; i++)
    {
        int u, v; cin>>u>>v;
        grane.pb({u, v});
        cnt[u][a[v]]++;
        cnt[v][a[u]]++;
    }

    for (auto par:grane)
    {
        int u=par.xx, v=par.yy;
        if (a[u]==a[v]) continue;
        ress+=2;
        vector<int> boje;
        for (int i=1; i<=4; i++) if (a[u]!=i && a[v]!=i) boje.pb(i);
        int c1, c2;
        c1=boje[0]; c2=boje[1];
        ress+=2*((cnt[u][c1]*cnt[v][c2])+(cnt[u][c2]*cnt[v][c1]))+cnt[u][c1]+cnt[u][c2]+cnt[v][c1]+cnt[v][c2];
        //cout<<u<<" "<<v<<" "<<ress<<endl;
    }
    cout<<ress;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 0 / 30