oj.uz

답안 #58711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58711 2018-07-19T01:06:05 Z onjo0127(#1933) Paths (BOI18_paths) C++11
23 / 100
 508 ms 30220 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[300009];
int color[300009], ans, cnt[300009][11];
bool vs[300009], c[11];

void go(int now, int lft) {
    ++ans;
    if(lft == 0) return;
    vs[now] = 1; c[color[now]] = 1;
    for(auto &it : adj[now]) {
        if(!vs[it] && !c[color[it]]) {
            go(it, lft - 1);
        }
    }
    vs[now] = 0; c[color[now]] = 0;
}

int main() {
    int N, M, K;
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1; i<=N; i++) scanf("%d",&color[i]);
    for(int i=0; i<M; i++) {
        int u, v; scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        ++cnt[u][color[v]];
        ++cnt[v][color[u]];
    }
    if(K == 1) return !printf("0");
    if(N <= 100 && M <= 100 && K <= 4) {
        for(int i=1; i<=N; i++) go(i, K-1);
        printf("%d", ans - N);
    }
    else if(N <= 300000 && M <= 300000 && K <= 3) {
        int tmp = 1 ^ 2 ^ 3;
        for(int i=1; i<=N; i++) {
            for(auto &it : adj[i]) {
                if(color[i] != color[it]) {
                    ++ans;
                    if(K == 3) ans += cnt[it][tmp ^ color[i] ^ color[it]];
                }
            }
        }
        printf("%d", ans);
    }
    return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:22: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:23:34: 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",&color[i]);
                             ~~~~~^~~~~~~~~~~~~~~~
paths.cpp:25:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d",&u,&v);
                   ~~~~~^~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 11412 KB Output is correct
2 Correct 134 ms 11412 KB Output is correct
3 Correct 508 ms 30220 KB Output is correct
4 Correct 239 ms 30220 KB Output is correct
5 Correct 221 ms 30220 KB Output is correct
6 Incorrect 415 ms 30220 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7380 KB Output is correct
2 Correct 10 ms 7392 KB Output is correct
3 Correct 9 ms 7584 KB Output is correct
4 Correct 7 ms 7584 KB Output is correct
5 Correct 9 ms 7584 KB Output is correct
6 Correct 10 ms 7584 KB Output is correct
7 Correct 8 ms 7584 KB Output is correct
8 Correct 8 ms 7596 KB Output is correct
9 Correct 9 ms 7596 KB Output is correct
10 Correct 8 ms 7596 KB Output is correct
11 Correct 109 ms 11412 KB Output is correct
12 Correct 134 ms 11412 KB Output is correct
13 Correct 508 ms 30220 KB Output is correct
14 Correct 239 ms 30220 KB Output is correct
15 Correct 221 ms 30220 KB Output is correct
16 Incorrect 415 ms 30220 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 30220 KB Output isn't correct
2 Halted 0 ms 0 KB -