oj.uz

Submission #927133

# Submission time Handle Problem Language Result Execution time Memory
927133 2024-02-14T09:56:56 Z vjudge1 Paths (BOI18_paths) C++17
100 / 100
 221 ms 53840 KB 
/*
no more temmy :(
*/

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
// #include<icecream.hpp>
// using namespace icecream;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
// mt19937 rng(1983413);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=3e5+100;
const int M=1e3+1;
const int B=317;
const int mod=1e9+7;
const int INF=1e18;
const int lg=64;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-9;
int n,m,k;
int c[N];
vector<int>g[N];
bool mark[N];
int ans=0;
void dfs(int x){
    mark[c[x]]=1;
    ans++;
    for(auto i:g[x]){
        if(!mark[c[i]]){
            dfs(i);
        }
    }
    mark[c[x]]=0;
}
void solve1(){
    for(int i=1;i<=n;i++){
        dfs(i);
    }
    cout<<ans-n<<'\n';
}
void solve2(){
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            if(c[j]!=c[i]){
                ans++;
            }
        }
    }
    cout<<ans<<'\n';
}   
int d[N][6];
void solve3(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            d[i][j]=g[i].size();
        }
        for(auto j:g[i]){
            d[i][c[j]]--;
        }
    }
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            ans+=d[j][c[i]];
            ans++;
        }
    }
    cout<<ans<<'\n';
}
int d2[N][6];
void solve4(){
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            d[i][c[j]]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int l=1;l<=k;l++){
            for(auto j:g[i]){
                if(c[j]==l)continue;
                d2[i][l]+=(g[j].size()-d[j][c[i]]-d[j][l]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            ans+=(g[j].size()-d[j][c[i]]);
            ans++;
        }
    }
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            int x=d2[j][c[i]];
            // (g[j].size()-d[j][c[i]])*(g[k].size()-d[k][c[j]]-d[k][c[i]]);
            ans+=x;
        }
    }
    cout<<ans<<'\n';
}
int d3[N][6][6];
void solve5(){
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            d[i][c[j]]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int l=1;l<=k;l++){
            for(auto j:g[i]){
                if(c[j]==l)continue;
                d2[i][l]+=(g[j].size()-d[j][c[i]]-d[j][l]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            ans+=(g[j].size()-d[j][c[i]]);
            ans++;
        }
    }
    for(int i=1;i<=n;i++){
        for(auto j:g[i]){
            int x=d2[j][c[i]];
            // (g[j].size()-d[j][c[i]])*(g[k].size()-d[k][c[j]]-d[k][c[i]]);
            ans+=x;
        }
    }
    for(int i=1;i<=n;i++){
        for(int l=1;l<=k;l++){
            if(l==c[i])continue;
            for(int w=1;w<=k;w++){
                if(w==l||w==c[i])continue;
                for(auto j:g[i]){
                    if(w==c[j]||l==c[j])continue;
                    d3[i][l][w]+=(g[j].size()-d[j][l]-d[j][w]-d[j][c[i]]);
                }
            }
        }
    }
    // i,j,k,l,n
    // i,j,c[k],
    for(int i=1;i<=n;i++){
        // int cur=0;
        for(int l=1;l<=k;l++){
            if(l==c[i])continue;
            for(auto j:g[i]){
                if(c[j]==l)continue;
                ans+=d3[j][c[i]][l]*d[i][l];
                // cur+=d3[j][c[i]][l]*d[i][l];
            }
        }
        // cout<<cur<<' ';
    }
    cout<<ans<<'\n';
}
void test(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        if(c[x]!=c[y]){
            g[x].push_back(y);
            g[y].push_back(x);
        }
    }
    if(k==1){
        cout<<0<<'\n';
        return;
    }
    if(k==2){
        solve2();
        return;
    }
    if(k==3){
        solve3();
        return;
    }
    if(k==4){
        solve4();
        return;
    }
    if(k==5){
        solve5();
        return;
    }
    if(n<=100&&m<=100&&k<=5){
        solve1();
        return;
    }
}
/*
*/  
 
signed main(){

    // ic.prefix("debug->| ");
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    long long t2=1;
    //  cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
    
    return 0;
 
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 2 ms 8648 KB Output is correct
5 Correct 2 ms 8632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 18140 KB Output is correct
2 Correct 40 ms 16592 KB Output is correct
3 Correct 122 ms 33512 KB Output is correct
4 Correct 59 ms 12736 KB Output is correct
5 Correct 39 ms 8540 KB Output is correct
6 Correct 102 ms 27832 KB Output is correct
7 Correct 143 ms 33740 KB Output is correct
8 Correct 136 ms 34200 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 2 ms 8648 KB Output is correct
5 Correct 2 ms 8632 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 47 ms 18140 KB Output is correct
12 Correct 40 ms 16592 KB Output is correct
13 Correct 122 ms 33512 KB Output is correct
14 Correct 59 ms 12736 KB Output is correct
15 Correct 39 ms 8540 KB Output is correct
16 Correct 102 ms 27832 KB Output is correct
17 Correct 143 ms 33740 KB Output is correct
18 Correct 136 ms 34200 KB Output is correct
19 Correct 54 ms 18272 KB Output is correct
20 Correct 53 ms 16592 KB Output is correct
21 Correct 159 ms 33696 KB Output is correct
22 Correct 58 ms 12660 KB Output is correct
23 Correct 56 ms 8536 KB Output is correct
24 Correct 101 ms 27840 KB Output is correct
25 Correct 147 ms 33688 KB Output is correct
26 Correct 161 ms 34192 KB Output is correct
27 Correct 45 ms 19916 KB Output is correct
28 Correct 63 ms 18504 KB Output is correct
29 Correct 221 ms 46304 KB Output is correct
30 Correct 146 ms 32632 KB Output is correct
31 Correct 128 ms 33476 KB Output is correct
32 Correct 208 ms 46376 KB Output is correct
33 Correct 2 ms 10588 KB Output is correct
34 Correct 3 ms 12636 KB Output is correct
35 Correct 3 ms 10588 KB Output is correct
36 Correct 2 ms 8540 KB Output is correct
37 Correct 2 ms 8540 KB Output is correct
38 Correct 2 ms 12800 KB Output is correct
39 Correct 2 ms 10836 KB Output is correct
40 Correct 4 ms 12632 KB Output is correct
41 Correct 2 ms 10588 KB Output is correct
42 Correct 3 ms 10588 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 29 ms 14940 KB Output is correct
3 Correct 14 ms 15448 KB Output is correct
4 Correct 29 ms 20316 KB Output is correct
5 Correct 26 ms 20424 KB Output is correct
6 Correct 115 ms 53840 KB Output is correct
7 Correct 17 ms 15452 KB Output is correct
8 Correct 40 ms 25320 KB Output is correct
9 Correct 43 ms 25540 KB Output is correct
10 Correct 49 ms 26056 KB Output is correct
11 Correct 60 ms 33996 KB Output is correct
12 Correct 77 ms 43412 KB Output is correct
13 Correct 70 ms 34544 KB Output is correct
14 Correct 115 ms 53504 KB Output is correct
15 Correct 111 ms 53760 KB Output is correct
16 Correct 2 ms 10584 KB Output is correct
17 Correct 2 ms 12632 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 3 ms 8540 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 2 ms 10584 KB Output is correct
23 Correct 2 ms 12636 KB Output is correct
24 Correct 2 ms 10588 KB Output is correct
25 Correct 2 ms 10588 KB Output is correct