Submission #1095662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095662		ivaziva	Paths (BOI18_paths)	C++14	70 / 100	286 ms	59984 KiB

paths

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define MAXN 300001
#define MAXM 6

int n,m,k;
int a[MAXN];
vector<int> adj[MAXM][MAXN];
map<pair<int,int>,int> twonodes;

int32_t main()
{
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++) cin>>a[i];
    int ans1=n,ans2=0,ans3=0,ans4=0,ans5=0;
    for (int i=1;i<=m;i++)
    {
        int x,y;cin>>x>>y;
        if (a[x]==a[y]) continue;
        adj[a[y]][x].push_back(y);
        adj[a[x]][y].push_back(x);
        ans2++;
    }
    for (int i=1;i<=n;i++)
    {
        for (int prva=1;prva<=k;prva++)
        {
            if (prva==a[i]) continue;
            for (int druga=prva+1;druga<=k;druga++)
            {
                if (druga==a[i]) continue;
                ans3+=adj[prva][i].size()*adj[druga][i].size();
            }
            for (int node:adj[prva][i])
            {
                for (int druga=1;druga<=k;druga++)
                {
                    if (druga==a[i] or druga==prva or adj[druga][node].size()==0) continue;
                    if (twonodes.find({druga,prva})==twonodes.end()) twonodes[{druga,prva}]=adj[druga][node].size();
                    else twonodes[{druga,prva}]+=adj[druga][node].size();
                }
            }
        }
        for (auto&p:twonodes)
        {
            pair<int,int> boje=p.first;int br=p.second;
            for (int prva=1;prva<=k;prva++)
            {
                if (prva==a[i] or prva==boje.first or prva==boje.second) continue;
                ans4+=br*adj[prva][i].size();
                if (k!=5) continue;
                int boja=15-a[i]-boje.first-boje.second-prva;
                if (twonodes.find({prva,boja})!=twonodes.end()) ans5+=br*twonodes[{prva,boja}];
                if (twonodes.find({boja,prva})!=twonodes.end()) ans5+=br*twonodes[{boja,prva}];
            }
        }
        twonodes.clear();
    }
    ans4/=2;ans5/=2;
    if (k==1) cout<<0<<endl;
    else if (k==2) cout<<2*ans2<<endl;
    else if (k==3) cout<<2*(ans2+ans3)<<endl;
    else if (k==4) cout<<2*(ans2+ans3+ans4)<<endl;
    else cout<<2*(ans2+ans3+ans4+ans5)<<endl;
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int32_t main()':
paths.cpp:19:9: warning: unused variable 'ans1' [-Wunused-variable]
   19 |     int ans1=n,ans2=0,ans3=0,ans4=0,ans5=0;
      |         ^~~~

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