Submission #24032

#	Time	Username	Problem	Language	Result	Execution time	Memory
24032		jenkhai	Tropical Garden (IOI11_garden)	C++14	100 / 100	3538 ms	49736 KiB

garden

#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 (stderr)

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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31