Submission #1271968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271968		tredsused70	Tropical Garden (IOI11_garden)	C++20	Compilation error	0 ms	0 KiB

garden

const int nmax = 100000;

int nextv[nmax * 2], cnt[nmax * 2];
int visited[nmax * 2];
int target;
int n_;
int cycle[nmax * 2], dist1[nmax * 2], dist2[nmax * 2];

void fill_cycle_dist(int v) {
    if(v == target) {
        int nv = nextv[v];
        int cur = cycle[v] - 1;
        while(nv != v) {
            dist1[nv] = cur;
            cur--;
            nv = nextv[nv];
        }
    }
    if(v == target + n_) {
        int nv = nextv[v];
        int cur = cycle[v] - 1;
        while(nv != v) {
            dist2[nv] = cur;
            cur--;
            nv = nextv[nv];
        }
    }
    return ;
}

void dfs(int v) {
    int nv = nextv[v];
    if(v == target)
        dist1[v] = 0;
    if(v == target + n_)
        dist2[v] = 0;
    visited[v] = 1;
    if(visited[nv] == 2) {
        if(dist1[nv] != -1)
            dist1[v] = dist1[nv] + 1;
        if(dist2[nv] != -1)
            dist2[v] = dist2[nv] + 1;
        visited[v] = 2;
        return ;
    }
    if(visited[nv] == 1) {
        int len = 1;
        while(nv != v) {
            len++;
            nv = nextv[nv];
        }
        nv = nextv[v];
        cycle[v] = len;
        while(nv != v) {
            cycle[nv] = len;
            nv = nextv[nv];
        }
        fill_cycle_dist(v);
        visited[v] = 2;
        return ;
    }
    dfs(nv);
    visited[v] = 2;
    if(cycle[v]) {
        fill_cycle_dist(v);
        return ;
    }
    if(dist1[nv] != -1)
        dist1[v] = dist1[nv] + 1;
    if(dist2[nv] != -1)
        dist2[v] = dist2[nv] + 1;
    return ;
}

void answer(int m) {
    cout << m << " answer\n";
    return ;
}

void count_routes(int n, int m, int t, int edges[][2], int q, int query[]) {
    n_ = n;
    fill(nextv, nextv + nmax * 2, -1);
    fill(dist1, dist1 + nmax * 2, -1);
    fill(dist2, dist2 + nmax * 2, -1);
    fill(cnt, cnt + nmax * 2, 0);
    fill(cycle, cycle + nmax * 2, 0);
    fill(visited, visited + nmax * 2, 0);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < 2; j++) {
            if(nextv[edges[i][j]] == -1) {
                if(cnt[edges[i][j ^ 1]])
                    nextv[edges[i][j]] = edges[i][j ^ 1];
                else
                    nextv[edges[i][j]] = edges[i][j ^ 1] + n;
            }
            else {
                if(nextv[edges[i][j] + n] == -1) {
                    if(cnt[edges[i][j ^ 1]])
                        nextv[edges[i][j] + n] = edges[i][j ^ 1];
                    else
                        nextv[edges[i][j] + n] = edges[i][j ^ 1] + n;
                }
            }
        }
        cnt[edges[i][0]]++;
        cnt[edges[i][1]]++;
    }
    for(int i = 0; i < n; i++) {
        if(cnt[i] == 1)
            nextv[i + n] = nextv[i];
        //cout << i << " " << nextv[i] << " " << nextv[i + n] << "\n";
    }
    target = t;
    for(int i = 0; i < n; i++) {
        if(!visited[i])
            dfs(i);
    }
    //for(int i = 0; i < n; i++) {
        //cout << i << "\n" << dist1[i] << " " << dist2[i] << "\n";
    //}
    for(int i = 0; i < q; i++) {
        int ans = 0;
        for(int j = 0; j < n; j++) {
            if((dist1[j] == query[i]) || (dist1[j] >= 0 && dist1[j] < query[i] && cycle[t] && (query[i] - dist1[j]) % cycle[t] == 0))
                ans++;
            else
                if((dist2[j] == query[i]) || (dist2[j] >= 0 && dist2[j] < query[i] && cycle[t + n] && (query[i] - dist2[j]) % cycle[t + n] == 0))
                    ans++;
        }
        answer(ans);
    }
    return ;
}

Compilation message (stderr)

garden.cpp: In function 'void answer(int)':
garden.cpp:76:5: error: 'cout' was not declared in this scope
   76 |     cout << m << " answer\n";
      |     ^~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:82:5: error: 'fill' was not declared in this scope
   82 |     fill(nextv, nextv + nmax * 2, -1);
      |     ^~~~