oj.uz

Submission #986234

# Submission time Handle Problem Language Result Execution time Memory
986234 2024-05-20T06:13:11 Z Aiperiii Paths (BOI18_paths) C++14
20 / 100
 255 ms 25176 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=3e5+5;
int cl[N];
vector <int> g[N];
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)cin>>cl[i];
    while(m--){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    int ans=0;
    if(k>=2){
        for(int i=1;i<=n;i++){
            for(auto to : g[i]){
                if(cl[i]!=cl[to])ans++;
            }
        }
    }
    if(k>=3){
        for(int i=1;i<=n;i++){
            vector <int> cnt(k+1);
            for(auto to : g[i]){
                cnt[cl[to]]++;
            }
            for(int a=1;a<=k;a++){
                for(int b=1;b<=k;b++){
                    if(a!=b && a!=cl[i] && b!=cl[i])ans+=cnt[a]*cnt[b];
                }
            }
        }
    }
    cout<<ans<<"\n";
}

/*
4 3 3
1 2 1 3
1 2
2 3
4 2
 
 
9 11 1
1 1 1 1 1 1 1 1 1
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8
*/

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 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 117 ms 18228 KB Output is correct
2 Correct 115 ms 18032 KB Output is correct
3 Correct 244 ms 24780 KB Output is correct
4 Correct 138 ms 20280 KB Output is correct
5 Correct 159 ms 20104 KB Output is correct
6 Correct 209 ms 21948 KB Output is correct
7 Correct 255 ms 24656 KB Output is correct
8 Correct 251 ms 25176 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 29 ms 11744 KB Output isn't correct
3 Halted 0 ms 0 KB -