제출 #74467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74467		win11905	Paths (BOI18_paths)	C++11	100 / 100	519 ms	173612 KiB

paths

#include <bits/stdc++.h>
using namespace std;

#define long long long

const int N = 3e5+5;
const int bit = 5;

int n, m, k, col[N];
long d[N][1<<bit];
vector<int> g[N], eb[bit+1];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= n; ++i) scanf("%d", col+i), col[i]--;
    for(int i = 0, u, v; i < m; ++i) {
        scanf("%d %d", &u, &v);
        g[u].emplace_back(v), g[v].emplace_back(u);
    }
    for(int i = 0; i < (1<<k); ++i) {
        int cnt = 0;
        for(int j = 0; j < k; ++j) if(i >> j & 1) cnt++;
        eb[cnt].emplace_back(i);
    }
    for(int i = 1; i <= n; ++i) d[i][1<<col[i]] = 1;
    long sum = 0;
    for(int i = 2; i <= k; ++i) for(auto x : eb[i]) {
        for(int i = 1; i <= n; ++i) {
            if(x & (1 << col[i])) for(auto v : g[i]) d[i][x] += d[v][x ^ (1<<col[i])]; 
            sum += d[i][x];
        }
    }
    printf("%lld\n", sum);
}

컴파일 시 표준 에러 (stderr) 메시지

paths.cpp: In function 'int main()':
paths.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:15:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", col+i), col[i]--;
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~
paths.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

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