Submission #1156815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156815		the_ZHER	Paths (BOI18_paths)	C++20	43 / 100	3095 ms	36736 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];
int cnt5[N][5];
int ans=0;
vector<pair<int,int> >v3;
signed main(){
boost;
    int n,m,k;
    cin>>n>>m>>k;
    v.push_back(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;
        v3.push_back({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){
    for(int i=1;i<=n;i++){
        for(int j=0;j<v1[i].size();j++){
            cnt5[i][v[v1[i][j]]]++;
        }
    }
    for(int i=0;i<v3.size();i++){
        int x=v3[i].first;
        int y=v3[i].second;
        if(v[x]==v[y]){
            continue;
        }
        cnt5[x][v[y]]--;
        int cnt1=v1[x].size()-1;
        for(int j=0;j<v1[y].size();j++){
            if(v1[y][j]==x){
                continue;
            }
            int z=v1[y][j];
            if(v[z]!=v[x]&&v[z]!=v[y]){
            ans+=(cnt1-cnt5[x][v[x]]-cnt5[x][v[y]]-cnt5[x][v[z]])*2;
            }
        }
        cnt5[x][v[y]]++;
    }
}
    cout<<ans;
}  

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