제출 #185212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
185212		Ruxandra985	Paths (BOI18_paths)	C++14	100 / 100	638 ms	77304 KiB

paths

#include <bits/stdc++.h>
 
using namespace std;
deque <pair <int,int> > dq;
long long dp[32][300010];
int cul[300010] , f[32][300010];
vector <int> v[300010];
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;
}

컴파일 시 표준 에러 (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: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30