oj.uz

Submission #24032

# Submission time Handle Problem Language Result Execution time Memory
24032 2017-05-29T17:03:51 Z jenkhai Tropical Garden (IOI11_garden) C++14
100 / 100
 3538 ms 49736 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
vector<vi> adj, F, adj2;
vi seen;
int C[3];
int N,P;

void join(int u, int v) {
    if(seen[u] == 0) {
        if(seen[v] == 0) adj[u].push_back(v+N);
        else adj[u].push_back(v);
    } else if(seen[u] == 1) {
        if(seen[v] == 0) adj[u+N].push_back(v+N);
        else adj[u+N].push_back(v);
    } 
}

void dfs(int u, int p, int idx) {
    for(int i=0;i<adj2[u].size();i++) {
        int v = adj2[u][i];
        if(v==p) {
            C[idx] = F[idx][u]+1;
        } else if(F[idx][v] == -1){
            F[idx][v] = F[idx][u]+1;
            dfs(v, p, idx);
        }
    }
}

void precompute() {
    F.assign(2, vi());
    for(int i=0;i<2;i++) {
        F[i].assign(2*N, -1);
        C[i] = 0;
    }
    F[0][P] = 0;
    dfs(P, P, 0);
    F[1][P+N] = 0;
    dfs(P+N, P+N, 1);
}

vi prev;

int solve(int k) {
    int ans = 0;
    for(int i=0;i<N;i++) {
        bool ok = false;
        for(int j=0;j<2;j++) {
            if(F[j][i] == -1) continue;
            else if(F[j][i] == k) {
                //printf("MATCH: i=%d\n", i);
                ok = true;
            }
            else if(C[j] && k>F[j][i] && (k-F[j][i])%C[j]==0) {
                //printf("CYCLE: i=%d C[j]=%d\n", i, C[j]);
                ok = true;
            }
        }
        if(ok) ans++;
    }
    return ans;
}

void count_routes(int _N, int M, int _P, int R[][2], int Q, int G[]) {
    P = _P;
    N = _N;
    adj.assign(2*N, vi());
    adj2.assign(2*N, vi());
    seen.assign(2*N, 0);
    for(int i=0;i<M;i++) {
        int u = R[i][0];
        int v = R[i][1];
        join(u,v);
        join(v,u);
        seen[u]++;
        seen[v]++;
    }
    for(int i=0;i<N;i++) {
        if(adj[i].size() == 0 && adj[i+N].size() == 1) adj[i].push_back(adj[i+N][0]);
        if(adj[i].size() == 1 && adj[i+N].size() == 0) adj[i+N].push_back(adj[i][0]);
    }
    for(int u=0;u<2*N;u++) {
        adj2[adj[u][0]].push_back(u);
    }
    //for(int i=0;i<N;i++) {
    //    if(adj2[i][0] >= N) printf("%d -> %d'\n", i, adj2[i][0]-N);
    //    else printf("%d -> %d\n", i, adj2[i][0]);
    //}
    //for(int i=N;i<2*N;i++) {
    //    if(adj2[i][0] >= N) printf("%d'-> %d'\n", i-N, adj2[i][0]-N);
    //    else printf("%d'-> %d\n", i-N, adj2[i][0]);
    //}
    precompute();

    for(int q=0;q<Q;q++) {
        answer(solve(G[q]));
    }
}

Compilation message

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj2[u].size();i++) {
                 ~^~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 5 ms 636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 5 ms 636 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 18 ms 5596 KB Output is correct
12 Correct 40 ms 8924 KB Output is correct
13 Correct 78 ms 35056 KB Output is correct
14 Correct 160 ms 30444 KB Output is correct
15 Correct 193 ms 30756 KB Output is correct
16 Correct 144 ms 21464 KB Output is correct
17 Correct 127 ms 18128 KB Output is correct
18 Correct 43 ms 9284 KB Output is correct
19 Correct 149 ms 30736 KB Output is correct
20 Correct 193 ms 31176 KB Output is correct
21 Correct 154 ms 21760 KB Output is correct
22 Correct 136 ms 18416 KB Output is correct
23 Correct 169 ms 33984 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 5 ms 636 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 18 ms 5596 KB Output is correct
12 Correct 40 ms 8924 KB Output is correct
13 Correct 78 ms 35056 KB Output is correct
14 Correct 160 ms 30444 KB Output is correct
15 Correct 193 ms 30756 KB Output is correct
16 Correct 144 ms 21464 KB Output is correct
17 Correct 127 ms 18128 KB Output is correct
18 Correct 43 ms 9284 KB Output is correct
19 Correct 149 ms 30736 KB Output is correct
20 Correct 193 ms 31176 KB Output is correct
21 Correct 154 ms 21760 KB Output is correct
22 Correct 136 ms 18416 KB Output is correct
23 Correct 169 ms 33984 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 162 ms 5920 KB Output is correct
26 Correct 251 ms 9476 KB Output is correct
27 Correct 2036 ms 35620 KB Output is correct
28 Correct 1706 ms 31420 KB Output is correct
29 Correct 2298 ms 31832 KB Output is correct
30 Correct 1456 ms 22480 KB Output is correct
31 Correct 1301 ms 19044 KB Output is correct
32 Correct 270 ms 9492 KB Output is correct
33 Correct 1709 ms 31156 KB Output is correct
34 Correct 2211 ms 31400 KB Output is correct
35 Correct 1439 ms 21784 KB Output is correct
36 Correct 1957 ms 18828 KB Output is correct
37 Correct 1421 ms 34684 KB Output is correct
38 Correct 3538 ms 49736 KB Output is correct