Submission #1156767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156767		the_ZHER	Paths (BOI18_paths)	C++20	20 / 100	165 ms	20820 KiB

paths

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e17;
const int N=3e5+5;
const int N1=1e5+5;
const int N2=5e6+6;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int d,in;
};
struct edge1{
    int l,r;
};
vector<int>v;
vector<int>v1[N];
vector<int>v2;
int dp[5][5];
int cnt[5];
signed main(){
boost;
    int n,m,k;
    cin>>n>>m>>k;
    v.push_back(0);
    int ans=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
        if(k>=2&&v[x]!=v[y]){
            ans+=2;
        }
        dp[v[x]][v[y]]++;
        dp[v[y]][v[x]]++;
    }
    if(k>=3){
        for(int i=1;i<=n;i++){
            for(int j=0;j<v1[i].size();j++){
                cnt[v[v1[i][j]]]++;
            }
            int cnt1=v1[i].size();
            if(cnt1==1){
                cnt[1]=0;
                cnt[2]=0;
                cnt[3]=0;
                cnt[4]=0;
                continue;
            }
            for(int j=0;j<v1[i].size();j++){
                int x=v1[i][j];
                if(v[x]!=v[i]){
                    ans+=(cnt1-cnt[v[x]]-cnt[v[i]])*2;
                }
                cnt1--;
                cnt[v[x]]--;
            }
            cnt[1]=0;
            cnt[2]=0;
            cnt[3]=0;
            cnt[4]=0;
        }
    }
if(k>=4){
    v2.push_back(1);
    v2.push_back(2);
    v2.push_back(3);
    v2.push_back(4);
    do{
        int cnt=dp[v2[0]][v2[1]];
        int cnt1=dp[v2[1]][v2[2]];
        int cnt2=dp[v2[2]][v2[3]];
        if(cnt1>0){
        ans+=cnt*cnt2;
        }
    }while(next_permutation(v2.begin(),v2.end()));
}
    cout<<ans;
}  

• Subtask 1: 0 / 23
• Subtask 2: 20 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30