Submission #65621

# Submission time Handle Problem Language Result Execution time Memory
65621 2018-08-08T09:22:35 Z mhnd Tropical Garden (IOI11_garden) C++14
Compilation error
0 ms 0 KB
#include "garden.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 3e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

vector<int> g[N],g2[N];
int n,d[2][N],to[N],fr[2],frd[2][2];
bool vis[N];

bool go(int t,int rem){
    if(!rem)return 1;
    if(rem < 0 || fr[t])return 0;
    if(fr[t] == t)return (rem%frd[t][t])==0;
    rem %= frd[t][!t] + frd[!t][t];
    return go(!t,rem - frd[t][!t]);
}

void bfs(int s,int t){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    d[t][s] = 0;
    while(q.size()){
        int u = q.front();
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i=0;i<g[u].size();i++){
            int v = g[u][i];
            if(d[t][v] != -1)continue;
            d[t][v] = d[t][u] + 1;
            q.push(v);
        }
    }
}

void cycle(int s,int t){
    memset(vis,0,sizeof(vis));
    int cur = to[s];
    int d = 1;
    while(!vis[cur]){
        if(cur == s){
            fr[t] = 0;
            frd[t][0] = d;
            break;
        }
        if(cur == (s+n)%n){
            fr[t] = 1;
            frd[t][1] = d;
            break;
        }
        d++;
        cur = to[cur];
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N;
    for(int i=0;i<M;i++){
        int u = R[i][0];
        int v = R[i][1];
        if(g[u].size() < 2)g[u].push_back(v);
        if(g[v].size() < 2)g[v].push_back(u);
    }
    for(int i=n;i<2*n;i++){
        g[i] = g[i-n];
        if(g[i].size() == 2)swap(g[i][0],g[i][1]);
    }
    for(int i=0;i<2*n;i++){
        int v = g[i][0];
        if(g[v][0] == i%n)v += n;
        to[i] = v;
        g2[v].push_back(i);
    }
    memset(d,-1,sizeof(d));
    memset(frd,-1,sizeof(frd));
    fr[0] = fr[1] = -1;
    bfs(P,0);
    bfs(P+n,1);
    cycle(P,0);
    cycle(P+n,1);
    for(int i=0;i<Q;i++){
        int dist = G[i];
        int ans = 0;
        for(int j=0;j<n;j++){
            bool o=0,t=0;
            if(d[0][j] != -1){
                int rem = dist - d[0][j];
                o = go(0,rem);
            }
            if(d[1][j] != -1){
                int rem = dist - d[1][j];
                t = go(1,rem);
            }
            ans += o|t;
        }
        answer(ans);
    }
}

Compilation message

garden.cpp: In function 'void bfs(int, int)':
garden.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[u].size();i++){
                     ~^~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:103:9: error: 'answer' was not declared in this scope
         answer(ans);
         ^~~~~~
garden.cpp:103:9: note: suggested alternative: 'ans'
         answer(ans);
         ^~~~~~
         ans