oj.uz

Submission #431478

# Submission time Handle Problem Language Result Execution time Memory
431478 2021-06-17T12:08:08 Z mat_v Tropical Garden (IOI11_garden) C++14
100 / 100
 232 ms 53912 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18184 KB Output is correct
2 Correct 13 ms 17980 KB Output is correct
3 Correct 14 ms 18008 KB Output is correct
4 Correct 12 ms 17964 KB Output is correct
5 Correct 13 ms 17868 KB Output is correct
6 Correct 14 ms 18268 KB Output is correct
7 Correct 13 ms 18000 KB Output is correct
8 Correct 15 ms 17996 KB Output is correct
9 Correct 17 ms 18228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18184 KB Output is correct
2 Correct 13 ms 17980 KB Output is correct
3 Correct 14 ms 18008 KB Output is correct
4 Correct 12 ms 17964 KB Output is correct
5 Correct 13 ms 17868 KB Output is correct
6 Correct 14 ms 18268 KB Output is correct
7 Correct 13 ms 18000 KB Output is correct
8 Correct 15 ms 17996 KB Output is correct
9 Correct 17 ms 18228 KB Output is correct
10 Correct 12 ms 17868 KB Output is correct
11 Correct 26 ms 20268 KB Output is correct
12 Correct 44 ms 22120 KB Output is correct
13 Correct 112 ms 45996 KB Output is correct
14 Correct 170 ms 31624 KB Output is correct
15 Correct 232 ms 32396 KB Output is correct
16 Correct 149 ms 29340 KB Output is correct
17 Correct 124 ms 27752 KB Output is correct
18 Correct 47 ms 22092 KB Output is correct
19 Correct 191 ms 31648 KB Output is correct
20 Correct 195 ms 32464 KB Output is correct
21 Correct 159 ms 28968 KB Output is correct
22 Correct 154 ms 27572 KB Output is correct
23 Correct 163 ms 32964 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18184 KB Output is correct
2 Correct 13 ms 17980 KB Output is correct
3 Correct 14 ms 18008 KB Output is correct
4 Correct 12 ms 17964 KB Output is correct
5 Correct 13 ms 17868 KB Output is correct
6 Correct 14 ms 18268 KB Output is correct
7 Correct 13 ms 18000 KB Output is correct
8 Correct 15 ms 17996 KB Output is correct
9 Correct 17 ms 18228 KB Output is correct
10 Correct 12 ms 17868 KB Output is correct
11 Correct 26 ms 20268 KB Output is correct
12 Correct 44 ms 22120 KB Output is correct
13 Correct 112 ms 45996 KB Output is correct
14 Correct 170 ms 31624 KB Output is correct
15 Correct 232 ms 32396 KB Output is correct
16 Correct 149 ms 29340 KB Output is correct
17 Correct 124 ms 27752 KB Output is correct
18 Correct 47 ms 22092 KB Output is correct
19 Correct 191 ms 31648 KB Output is correct
20 Correct 195 ms 32464 KB Output is correct
21 Correct 159 ms 28968 KB Output is correct
22 Correct 154 ms 27572 KB Output is correct
23 Correct 163 ms 32964 KB Output is correct
24 Correct 16 ms 17996 KB Output is correct
25 Correct 26 ms 20548 KB Output is correct
26 Correct 45 ms 22076 KB Output is correct
27 Correct 118 ms 46104 KB Output is correct
28 Correct 170 ms 31624 KB Output is correct
29 Correct 203 ms 32584 KB Output is correct
30 Correct 170 ms 29332 KB Output is correct
31 Correct 168 ms 27852 KB Output is correct
32 Correct 48 ms 22172 KB Output is correct
33 Correct 148 ms 31676 KB Output is correct
34 Correct 232 ms 32568 KB Output is correct
35 Correct 171 ms 29012 KB Output is correct
36 Correct 140 ms 27828 KB Output is correct
37 Correct 178 ms 32968 KB Output is correct
38 Correct 222 ms 53912 KB Output is correct