제출 #198101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198101		Andrei_Cotor	Paths (BOI18_paths)	C++14	100 / 100	471 ms	56824 KiB

paths

#include<iostream>
#include<vector>

using namespace std;

long long Dp[35][300005];
int Col[300005];
vector<int> A[300005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m,k;
    cin>>n>>m>>k;

    for(int i=1; i<=n; i++)
    {
        cin>>Col[i];
        Col[i]--;
        Dp[1<<Col[i]][i]=1;
    }

    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;

        A[x].push_back(y);
        A[y].push_back(x);
    }

    long long rez=0;
    for(int conf=1; conf<(1<<k); conf++)  //tot timpul o sa parcurg config din care se poate obtine conf inainte de conf
    {
        for(int i=1; i<=n; i++)
        {
            if(Dp[conf][i]==0)
                continue;

            rez+=Dp[conf][i];

            for(auto other:A[i])
            {
                if(conf&(1<<Col[other]))
                    continue;
                Dp[conf^(1<<Col[other])][other]+=Dp[conf][i];
            }
        }
    }

    cout<<rez-n<<"\n";
    return 0;
}

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