oj.uz

Submission #927097

# Submission time Handle Problem Language Result Execution time Memory
927097 2024-02-14T09:10:07 Z vjudge1 Paths (BOI18_paths) C++17
43 / 100
 145 ms 30036 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][5];
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';
}
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(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 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10584 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 44 ms 18268 KB Output is correct
2 Correct 35 ms 14520 KB Output is correct
3 Correct 108 ms 29412 KB Output is correct
4 Correct 59 ms 14676 KB Output is correct
5 Correct 37 ms 10588 KB Output is correct
6 Correct 88 ms 25536 KB Output is correct
7 Correct 105 ms 29520 KB Output is correct
8 Correct 113 ms 30036 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 44 ms 18268 KB Output is correct
12 Correct 35 ms 14520 KB Output is correct
13 Correct 108 ms 29412 KB Output is correct
14 Correct 59 ms 14676 KB Output is correct
15 Correct 37 ms 10588 KB Output is correct
16 Correct 88 ms 25536 KB Output is correct
17 Correct 105 ms 29520 KB Output is correct
18 Correct 113 ms 30036 KB Output is correct
19 Correct 44 ms 18260 KB Output is correct
20 Correct 34 ms 14932 KB Output is correct
21 Correct 126 ms 29520 KB Output is correct
22 Correct 55 ms 14748 KB Output is correct
23 Correct 38 ms 10724 KB Output is correct
24 Correct 83 ms 25460 KB Output is correct
25 Correct 145 ms 29524 KB Output is correct
26 Correct 122 ms 29864 KB Output is correct
27 Incorrect 35 ms 17824 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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