oj.uz

Submission #58710

# Submission time Handle Problem Language Result Execution time Memory
58710 2018-07-19T01:03:57 Z onjo0127(#1933) Paths (BOI18_paths) C++11
23 / 100
 469 ms 30188 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(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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 7 ms 7452 KB Output is correct
4 Correct 7 ms 7468 KB Output is correct
5 Correct 10 ms 7596 KB Output is correct
6 Correct 8 ms 7596 KB Output is correct
7 Correct 8 ms 7684 KB Output is correct
8 Correct 8 ms 7684 KB Output is correct
9 Correct 8 ms 7684 KB Output is correct
10 Correct 7 ms 7700 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 11632 KB Output is correct
2 Correct 80 ms 11632 KB Output is correct
3 Correct 469 ms 30188 KB Output is correct
4 Correct 219 ms 30188 KB Output is correct
5 Correct 204 ms 30188 KB Output is correct
6 Incorrect 337 ms 30188 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 7 ms 7452 KB Output is correct
4 Correct 7 ms 7468 KB Output is correct
5 Correct 10 ms 7596 KB Output is correct
6 Correct 8 ms 7596 KB Output is correct
7 Correct 8 ms 7684 KB Output is correct
8 Correct 8 ms 7684 KB Output is correct
9 Correct 8 ms 7684 KB Output is correct
10 Correct 7 ms 7700 KB Output is correct
11 Correct 107 ms 11632 KB Output is correct
12 Correct 80 ms 11632 KB Output is correct
13 Correct 469 ms 30188 KB Output is correct
14 Correct 219 ms 30188 KB Output is correct
15 Correct 204 ms 30188 KB Output is correct
16 Incorrect 337 ms 30188 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 30188 KB Output isn't correct
2 Halted 0 ms 0 KB -