Submission #431478

#	Time	Username	Problem	Language	Result	Execution time	Memory
431478		mat_v	Tropical Garden (IOI11_garden)	C++14	100 / 100	232 ms	53912 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define maxN 150005
#define pb push_back

using namespace std;


int n,m;
int p;
int q;
vector<int> _graf[maxN];
int slika[2 * maxN];
vector<int> graf[2 * maxN];
int najv[maxN];

int da(int x, int y){
    if(najv[x] == y)return 1;
    return 0;
}

int kveri[maxN];

int ans[maxN];
bool bio[2 * maxN];

vector<int> v[2 * maxN];
map<int,int> has;
int duz;

void dfs(int x, int y){
    if(x <= n){
        has[y]++;
        v[y%duz].pb(y);
    }
    bio[x] = 1;
    for(auto c:graf[x]){
        if(bio[c])continue;
        dfs(c,y+1);
    }
}

void resi(int x){
    ff(i,1,2*n)bio[i] = 0;

    int poc = x;

    duz = 0;

    while(1){
        if(bio[poc])break;
        bio[poc] = 1;
        duz++;
        poc = slika[poc];
    }
    bool ciklus = 0;
    if(poc == x)ciklus = 1;
    ff(i,0,2*n)v[i].clear();
    ff(i,0,2*n)bio[i] = 0;
    has.clear();
    dfs(x,0);
    ff(i,0,duz - 1)sort(v[i].begin(), v[i].end());
    ff(i,1,q){
        if(!ciklus){
            ans[i] += (has[kveri[i]]);
        }
        else{
            int koji = kveri[i]%duz;
            int kurac = v[koji].size();
            if(!kurac)continue;
            if(v[koji][kurac - 1] < koji)ans[i] += kurac;
            else{
                auto it = upper_bound(v[koji].begin(), v[koji].end(), kveri[i]);
                ans[i] += (it - v[koji].begin());

            }


        }
    }
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N;
    m = M;
    q = Q;
    ff(i,0,q - 1)kveri[i + 1] = G[i];
    ff(i,0,m - 1){
        R[i][0]++;
        R[i][1]++;
        _graf[R[i][0]].pb(R[i][1]);
        _graf[R[i][1]].pb(R[i][0]);
        if(najv[R[i][0]] == 0)najv[R[i][0]] = R[i][1];
        if(najv[R[i][1]] == 0)najv[R[i][1]] = R[i][0];
    }
    ff(i,1,n){
        int p1 = _graf[i].size();
        if(p1 == 1){
            slika[i] = slika[i + n] = _graf[i][0] + n*da(_graf[i][0], i);
            int p2 = _graf[i][0] + n*da(_graf[i][0], i);
            graf[p2].pb(i);
            graf[p2].pb(i + n);
        }
        else{
            slika[i] = _graf[i][0] + n*da(_graf[i][0], i);
            slika[i + n] = _graf[i][1] + n*da(_graf[i][1], i);
            int p2 = _graf[i][0] + n*da(_graf[i][0], i);
            int p3 = _graf[i][1] + n*da(_graf[i][1], i);
            graf[p2].pb(i);
            graf[p3].pb(i + n);
        }
    }
    p = P+1;
    resi(p);
    resi(p + n);
    ff(i,1,q)answer(ans[i]);
}
/*

6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2

*/

Compilation message (stderr)

garden.cpp: In function 'void resi(int)':
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:47:5: note: in expansion of macro 'ff'
   47 |     ff(i,1,2*n)bio[i] = 0;
      |     ^~
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:61:5: note: in expansion of macro 'ff'
   61 |     ff(i,0,2*n)v[i].clear();
      |     ^~
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:62:5: note: in expansion of macro 'ff'
   62 |     ff(i,0,2*n)bio[i] = 0;
      |     ^~
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:65:5: note: in expansion of macro 'ff'
   65 |     ff(i,0,duz - 1)sort(v[i].begin(), v[i].end());
      |     ^~
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:66:5: note: in expansion of macro 'ff'
   66 |     ff(i,1,q){
      |     ^~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:92:5: note: in expansion of macro 'ff'
   92 |     ff(i,0,q - 1)kveri[i + 1] = G[i];
      |     ^~
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:93:5: note: in expansion of macro 'ff'
   93 |     ff(i,0,m - 1){
      |     ^~
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:101:5: note: in expansion of macro 'ff'
  101 |     ff(i,1,n){
      |     ^~
garden.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
garden.cpp:121:5: note: in expansion of macro 'ff'
  121 |     ff(i,1,q)answer(ans[i]);
      |     ^~

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