oj.uz

Submission #598470

# Submission time Handle Problem Language Result Execution time Memory
598470 2022-07-18T11:41:46 Z urosk Paths (BOI18_paths) C++14
20 / 100
 312 ms 39248 KB 
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 300005
#define maxk 6
ll n,m,k;
ll ans = 0;
vector<ll> g[maxn];
ll a[maxn];
ll dp[maxn][maxk][maxk];
ll cnt[maxn][maxk];
void kraj(){
    cout<<ans<<endl;
    exit(0);
}
int main(){
	daj_mi_malo_vremena
    cin >> n >> m >> k;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    for(ll i = 1;i<=m;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    if(k==1) kraj();
    ll cur = 0;
    for(ll i = 1;i<=n;i++){
        for(ll j : g[i]){
            if(a[i]==a[j]) continue;
            cnt[i][a[j]]++;
            cur++;
        }
    }
    ans+=cur;
    if(k==2) kraj();
    cur = 0;
    for(ll i = 1;i<=n;i++){
        vector<ll> v(k+1);
        for(ll j : g[i]){
            v[a[j]]++;
        }
        ll coli = a[i];
        for(ll e = 1;e<=k;e++){
            for(ll r = e+1;r<=k;r++){
                if(e==coli||r==coli) continue;
                cur+=v[e]*v[r];
            }
        }
    }
    ans+=2*cur;
    if(k==3) kraj();
    for(ll i = 1;i<=n;i++){
        for(ll j : g[i]){
            ll coli = a[i];
            ll colj = a[j];
            for(ll e = 1;e<=k;e++){
                dp[i][colj][e] += cnt[j][e];
                if(e==coli) dp[i][colj][e]--;
            }
        }
    }
	return 0;
}
/*
4 3 3
1 2 1 3
1 2
2 3
4 2
*/

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 17616 KB Output is correct
2 Correct 56 ms 16812 KB Output is correct
3 Correct 312 ms 38788 KB Output is correct
4 Correct 116 ms 20496 KB Output is correct
5 Correct 104 ms 19020 KB Output is correct
6 Correct 225 ms 31220 KB Output is correct
7 Correct 303 ms 38780 KB Output is correct
8 Correct 280 ms 39248 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -