Submission #185209

#	Time	Username	Problem	Language	Result	Execution time	Memory
185209		Ruxandra985	Paths (BOI18_paths)	C++14	53 / 100	251 ms	44820 KiB

paths

#include <bits/stdc++.h>

using namespace std;
deque <pair <int,int> > dq;
long long dp[32][100010];
int cul[100010] , f[32][100010];
vector <int> v[100010];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , j , nod , vecin , conf , x, y;
    long long sol;
    fscanf (fin,"%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d",&cul[i]);
        cul[i]--;
        dp[(1 << cul[i])][i] = 1;
        f[(1 << cul[i])][i] = 1;
        dq.push_back(make_pair((1 << cul[i]) , i));
    }
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    while (!dq.empty()){
        conf = dq.front().first;
        nod = dq.front().second;
        dq.pop_front();
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            if ((conf & ( 1 << cul[vecin])) == 0){
                dp[(conf | ( 1 << cul[vecin]))][vecin] += dp[conf][nod];
                if (!f[(conf | ( 1 << cul[vecin]))][vecin]){
                    f[(conf | ( 1 << cul[vecin]))][vecin] = 1;
                    dq.push_back(make_pair( (conf | ( 1 << cul[vecin])) , vecin ));
                }
            }
        }
    }
    sol = 0;
    for (i=0;i<32;i++)
        for (j=1;j<=n;j++)
            sol+=dp[i][j];
    fprintf (fout,"%lld",sol - n);
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
paths.cpp:14:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&m,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:16:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&cul[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
paths.cpp:23:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

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