oj.uz

Submission #927104

# Submission time Handle Problem Language Result Execution time Memory
927104 2024-02-14T09:27:33 Z vjudge1 Paths (BOI18_paths) C++17
70 / 100
 221 ms 49488 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';
}

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(n<=100&&m<=100&&k<=4){
        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 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 12744 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 18140 KB Output is correct
2 Correct 35 ms 16636 KB Output is correct
3 Correct 127 ms 33576 KB Output is correct
4 Correct 58 ms 14700 KB Output is correct
5 Correct 40 ms 10588 KB Output is correct
6 Correct 100 ms 29560 KB Output is correct
7 Correct 108 ms 33360 KB Output is correct
8 Correct 118 ms 33872 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Correct 2 ms 12744 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12636 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 43 ms 18140 KB Output is correct
12 Correct 35 ms 16636 KB Output is correct
13 Correct 127 ms 33576 KB Output is correct
14 Correct 58 ms 14700 KB Output is correct
15 Correct 40 ms 10588 KB Output is correct
16 Correct 100 ms 29560 KB Output is correct
17 Correct 108 ms 33360 KB Output is correct
18 Correct 118 ms 33872 KB Output is correct
19 Correct 42 ms 18236 KB Output is correct
20 Correct 34 ms 16596 KB Output is correct
21 Correct 114 ms 33436 KB Output is correct
22 Correct 55 ms 14676 KB Output is correct
23 Correct 41 ms 10584 KB Output is correct
24 Correct 105 ms 29632 KB Output is correct
25 Correct 118 ms 33360 KB Output is correct
26 Correct 111 ms 33876 KB Output is correct
27 Correct 42 ms 19824 KB Output is correct
28 Correct 53 ms 20304 KB Output is correct
29 Correct 221 ms 49488 KB Output is correct
30 Correct 125 ms 36932 KB Output is correct
31 Correct 162 ms 37940 KB Output is correct
32 Correct 182 ms 49240 KB Output is correct
33 Correct 2 ms 12636 KB Output is correct
34 Correct 2 ms 12636 KB Output is correct
35 Correct 2 ms 12636 KB Output is correct
36 Correct 2 ms 10840 KB Output is correct
37 Correct 2 ms 10588 KB Output is correct
38 Correct 2 ms 12636 KB Output is correct
39 Correct 2 ms 12636 KB Output is correct
40 Correct 2 ms 12636 KB Output is correct
41 Correct 2 ms 12636 KB Output is correct
42 Correct 2 ms 12636 KB Output is correct

Subtask #4
0 / 30.0

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