답안 #968709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
968709	2024-04-23T22:25:14 Z	raphaelp	Paths (BOI18_paths)	C++14	100 / 100	499 ms	41600 KB

paths

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long N, M, K;
    cin >> N >> M >> K;
    vector<long long> C(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> C[i];
        C[i]--;
    }
    vector<vector<long long>> AR(N);
    vector<vector<long long>> voisins(N, vector<long long>(K));
    for (long long i = 0; i < M; i++)
    {
        long long a, b;
        cin >> a >> b;
        a--, b--;
        AR[a].push_back(b);
        AR[b].push_back(a);
        voisins[a][C[b]]++;
        voisins[b][C[a]]++;
    }
    long long tot = 0, half = 0;
    for (long long i = 0; i < N; i++)
    {
        vector<long long> count((1 << K));
        for (long long j = 0; j < AR[i].size(); j++)
        {
            count[(1 << C[AR[i][j]])]++;
            for (long long k = 0; k < K; k++)
            {
                if (k == C[AR[i][j]])
                    continue;
                count[((1 << C[AR[i][j]]) | (1 << k))] += voisins[AR[i][j]][k];
            }
        }
        for (long long j = 1; j < (1 << K); j++)
        {
            if (j & (1 << C[i]))
                continue;
            if (__builtin_popcount(j) > 2)
                continue;
            if (__builtin_popcount(j) == 1 && K >= 2)
                half += count[j];
            if (__builtin_popcount(j) == 1 && K >= 3)
            {
                for (long long k = 0; k < K; k++)
                {
                    if ((j & (1 << k)) || k == C[i])
                        continue;
                    half += count[(1 << k)] * count[j];
                }
            }
            if (__builtin_popcount(j) == 2 && K >= 4)
            {
                for (long long k = 0; k < K; k++)
                {
                    if ((j & (1 << k)) || k == C[i])
                        continue;
                    half += count[(1 << k)] * count[j];
                }
            }
            if (__builtin_popcount(j) == 2 && K >= 5)
            {
                half += count[j] * count[((1 << K) - 1 - j - (1 << C[i]))];
            }
        }
    }
    cout << tot * 2 + half;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:29:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (long long j = 0; j < AR[i].size(); j++)
      |                               ~~^~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	8020 KB	Output is correct
2	Correct	95 ms	7604 KB	Output is correct
3	Correct	461 ms	36688 KB	Output is correct
4	Correct	152 ms	11092 KB	Output is correct
5	Correct	177 ms	11020 KB	Output is correct
6	Correct	327 ms	26528 KB	Output is correct
7	Correct	478 ms	36776 KB	Output is correct
8	Correct	462 ms	37356 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	117 ms	8020 KB	Output is correct
12	Correct	95 ms	7604 KB	Output is correct
13	Correct	461 ms	36688 KB	Output is correct
14	Correct	152 ms	11092 KB	Output is correct
15	Correct	177 ms	11020 KB	Output is correct
16	Correct	327 ms	26528 KB	Output is correct
17	Correct	478 ms	36776 KB	Output is correct
18	Correct	462 ms	37356 KB	Output is correct
19	Correct	118 ms	7844 KB	Output is correct
20	Correct	95 ms	7368 KB	Output is correct
21	Correct	457 ms	36916 KB	Output is correct
22	Correct	165 ms	10932 KB	Output is correct
23	Correct	162 ms	11180 KB	Output is correct
24	Correct	344 ms	26384 KB	Output is correct
25	Correct	481 ms	36944 KB	Output is correct
26	Correct	446 ms	37088 KB	Output is correct
27	Correct	126 ms	7764 KB	Output is correct
28	Correct	128 ms	9812 KB	Output is correct
29	Correct	452 ms	41300 KB	Output is correct
30	Correct	292 ms	24356 KB	Output is correct
31	Correct	376 ms	24520 KB	Output is correct
32	Correct	499 ms	41600 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	0 ms	348 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	33 ms	2644 KB	Output is correct
3	Correct	32 ms	3308 KB	Output is correct
4	Correct	91 ms	13648 KB	Output is correct
5	Correct	88 ms	14220 KB	Output is correct
6	Correct	124 ms	15476 KB	Output is correct
7	Correct	32 ms	3164 KB	Output is correct
8	Correct	116 ms	15444 KB	Output is correct
9	Correct	102 ms	15812 KB	Output is correct
10	Correct	90 ms	16072 KB	Output is correct
11	Correct	67 ms	9164 KB	Output is correct
12	Correct	83 ms	12356 KB	Output is correct
13	Correct	84 ms	9416 KB	Output is correct
14	Correct	116 ms	15444 KB	Output is correct
15	Correct	122 ms	15324 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	344 KB	Output is correct

답안 #968709

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 20.0 / 20.0

Subtask #3 27.0 / 27.0

Subtask #4 30.0 / 30.0

Subtask #1
23.0 / 23.0

Subtask #2
20.0 / 20.0

Subtask #3
27.0 / 27.0

Subtask #4
30.0 / 30.0