oj.uz

Submission #650618

# Submission time Handle Problem Language Result Execution time Memory
650618 2022-10-14T09:42:50 Z PoonYaPat Tropical Garden (IOI11_garden) C++14
100 / 100
 2666 ms 56464 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

int n,m,dis1[300001],dis2[300001],cycle1,cycle2;
vector<int> adj[150001],adj2[300001],rev[300001];
bool vis[300001];

void new_graph(int now) {
    if (now>=n) {
        if (adj[now-n].size()>1) { //go second
            int des=adj[now-n][1];
            if (adj[des][0]==now-n) adj2[now].push_back(des+n);
            else adj2[now].push_back(des);
        } else { //go best
            int des=adj[now-n][0];
            if (adj[des][0]==now-n) adj2[now].push_back(des+n);
            else adj2[now].push_back(des);
        }
    } else { //go best
        int des=adj[now][0];
        if (adj[des][0]==now) adj2[now].push_back(des+n);
        else adj2[now].push_back(des);
    }
}

void dfs(int x, int step, int *dis, int &cycle_sz) {
    if (!vis[x]) {
        vis[x]=true;
        dis[x]=step;
        for (auto s : rev[x]) dfs(s,step+1,dis,cycle_sz);
    } else {
        cycle_sz=step;
    }
}

void count_routes(int N, int M, int P, int R[][2], int q, int g[]) {
    n=N; m=M;
    for (int i=0; i<m; ++i) {
        adj[R[i][0]].push_back(R[i][1]);
        adj[R[i][1]].push_back(R[i][0]);
    }
    for (int i=0; i<2*n; ++i) new_graph(i);
    for (int i=0; i<2*n; ++i) for (auto s : adj2[i]) rev[s].push_back(i);
    memset(dis1,0x3f,sizeof(dis1));
    memset(dis2,0x3f,sizeof(dis2));
    cycle1=cycle2=-1;

    dfs(P,0,dis1,cycle1);
    memset(vis,0,sizeof(vis));
    dfs(P+n,0,dis2,cycle2);

    for (int i=0; i<q; ++i) {
        int want=g[i],cnt=0;

        for (int node=0; node<n; ++node) {
            int have=false;

            if (dis1[node]==want) have=true;
            if (dis2[node]==want) have=true;
            if (cycle1!=-1 && want>=dis1[node] && (want-dis1[node])%cycle1==0) have=true;
            if (cycle2!=-1 && want>=dis2[node] && (want-dis2[node])%cycle2==0) have=true;

            if (have) ++cnt;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 10 ms 20652 KB Output is correct
3 Correct 10 ms 20692 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 11 ms 20496 KB Output is correct
6 Correct 12 ms 20820 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 12 ms 20692 KB Output is correct
9 Correct 13 ms 20812 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 10 ms 20652 KB Output is correct
3 Correct 10 ms 20692 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 11 ms 20496 KB Output is correct
6 Correct 12 ms 20820 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 12 ms 20692 KB Output is correct
9 Correct 13 ms 20812 KB Output is correct
10 Correct 12 ms 20564 KB Output is correct
11 Correct 24 ms 24012 KB Output is correct
12 Correct 45 ms 26504 KB Output is correct
13 Correct 59 ms 46156 KB Output is correct
14 Correct 134 ms 40716 KB Output is correct
15 Correct 150 ms 41112 KB Output is correct
16 Correct 162 ms 35524 KB Output is correct
17 Correct 105 ms 33532 KB Output is correct
18 Correct 38 ms 26444 KB Output is correct
19 Correct 128 ms 40652 KB Output is correct
20 Correct 165 ms 41028 KB Output is correct
21 Correct 137 ms 35420 KB Output is correct
22 Correct 121 ms 33548 KB Output is correct
23 Correct 158 ms 42700 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 10 ms 20652 KB Output is correct
3 Correct 10 ms 20692 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 11 ms 20496 KB Output is correct
6 Correct 12 ms 20820 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 12 ms 20692 KB Output is correct
9 Correct 13 ms 20812 KB Output is correct
10 Correct 12 ms 20564 KB Output is correct
11 Correct 24 ms 24012 KB Output is correct
12 Correct 45 ms 26504 KB Output is correct
13 Correct 59 ms 46156 KB Output is correct
14 Correct 134 ms 40716 KB Output is correct
15 Correct 150 ms 41112 KB Output is correct
16 Correct 162 ms 35524 KB Output is correct
17 Correct 105 ms 33532 KB Output is correct
18 Correct 38 ms 26444 KB Output is correct
19 Correct 128 ms 40652 KB Output is correct
20 Correct 165 ms 41028 KB Output is correct
21 Correct 137 ms 35420 KB Output is correct
22 Correct 121 ms 33548 KB Output is correct
23 Correct 158 ms 42700 KB Output is correct
24 Correct 11 ms 20564 KB Output is correct
25 Correct 115 ms 24148 KB Output is correct
26 Correct 183 ms 26552 KB Output is correct
27 Correct 2310 ms 46352 KB Output is correct
28 Correct 937 ms 40764 KB Output is correct
29 Correct 2625 ms 41164 KB Output is correct
30 Correct 1486 ms 35748 KB Output is correct
31 Correct 1481 ms 33648 KB Output is correct
32 Correct 148 ms 26564 KB Output is correct
33 Correct 939 ms 40756 KB Output is correct
34 Correct 2666 ms 41260 KB Output is correct
35 Correct 1665 ms 35476 KB Output is correct
36 Correct 1527 ms 33664 KB Output is correct
37 Correct 764 ms 42932 KB Output is correct
38 Correct 2033 ms 56464 KB Output is correct