Submission #63441

#	Time	Username	Problem	Language	Result	Execution time	Memory
63441		FLDutchman	Tropical Garden (IOI11_garden)	C++14	100 / 100	284 ms	40628 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define pb push_back
#define fst first
#define snd second
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define V vector

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

struct edge{
    int v, l;
    bool operator< (const edge &e){
        return l < e.l;
    }
};

V<V<edge>> graph;
vvi adj;

vi dists;
int dfs(int u, int depth, int p){
    //cout << "dfs " << u << " " << depth << " " << p << endl; 
    if(u == p and depth != 0) return depth;
    int ret = -1;
    dists[depth] += u&1;
    for(int v : adj[u]) ret = max(ret, dfs(v, depth+1, p));
    return ret;
}

void count_routes(INT N, INT M, INT P, INT R[][2], INT Q, INT G[]) {
    graph.resize(N);
    adj.resize(2*N);
    FOR(i, 0, M) {
        graph[R[i][0]].pb({R[i][1], i});
        graph[R[i][1]].pb({R[i][0], i});
    }
    FOR(i, 0, N) sort(graph[i].begin(), graph[i].end());
    FOR(i, 0, N){
        // 0 = from best, 1 = not from best
        // move from 2n+1 -> graph[n][0]
        // move from 2n -> graph[n][1], should it exist
        // We'll only store the opposite
        auto e1 = graph[i][0], e2 = graph[i][graph[i].size() > 1];
        int l1 = graph[e1.v][0].l, l2 = graph[e2.v][0].l;
        adj[  2*e1.v  + (e1.l != l1) ].pb(i<<1|1);
        adj[  2*e2.v  + (e2.l != l2) ].pb(i<<1);
    }
    vi answers(Q, 0);
    FOR(i, 0, 2){
        dists.assign(4*N, 0);
        int p = P<<1|i;
        int l = dfs(p, 0, p);
        //for(int k : dists) cout << k << " ";
        //cout << endl;
        //cout << l << endl;
        if(l != -1) FOR(i, l, dists.size()) dists[i] += dists[i-l];
        FOR(q, 0, Q) answers[q] += dists[ G[q] >= 4*N ? (G[q]-2*N)%l + 2*N : G[q] ]; 
    }
    FOR(i, 0, Q) answer(answers[i]); 
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(INT, INT, INT, INT (*)[2], INT, INT*)':
garden.cpp:12:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
garden.cpp:66:21: note: in expansion of macro 'FOR'
         if(l != -1) FOR(i, l, dists.size()) dists[i] += dists[i-l];
                     ^~~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31