oj.uz

Submission #14849

# Submission time Handle Problem Language Result Execution time Memory
14849 2015-06-30T16:58:51 Z gs14004 Tropical Garden (IOI11_garden) C++14
100 / 100
 2525 ms 33580 KB 
#include "garden.h"
#include "gardenlib.h"
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;

queue<int> q, p, d;
vector<int> ls;

vector<pi> graph[150005];
vector<int> graph1[300005];

int nxt[300005];
int low[150005];
int deg[300005];
int ped[300005];

bool vis[300005];
bool ans[150005];

void make_graph(int N, int M, int R[][2]){
    for (int i=0; i<M; i++) {
        for (int j=0; j<2; j++) {
            low[R[i][j]] = min(low[R[i][j]],i);
        }
        graph[R[i][0]].push_back(pi(R[i][1],i));
        graph[R[i][1]].push_back(pi(R[i][0],i));
    }
    for (int i=0; i<N; i++) {
        if(low[graph[i][0].first] == graph[i][0].second){
            nxt[2*i] = graph[i][0].first * 2 + 1;
        }
        else{
            nxt[2*i] = graph[i][0].first * 2;
        }
        if(graph[i].size() == 1){
            nxt[2*i+1] = nxt[2*i];
        }
        else{
            if(low[graph[i][1].first] == graph[i][1].second){
                nxt[2*i+1] = graph[i][1].first * 2 + 1;
            }
            else{
                nxt[2*i+1] = graph[i][1].first * 2;
            }
        }
    }
}

int dist0[150005], dist1[150005], peri0[150005], peri1[150005];

void solve(int x, int *dist, int *peri){
    memset(vis,0,sizeof(vis));
    q.push(x);
    p.push(-1);
    d.push(0);
    vis[x] = 1;
    while (!q.empty()) {
        int qf = q.front();
        int pf = p.front();
        int df = d.front();
        q.pop(), p.pop(), d.pop();
        pf = max(pf, ped[qf]);
        if(qf % 2 == 0){
            dist[qf/2] = df;
            peri[qf/2] = pf;
        }
        for (auto &i : graph1[qf]){
            if(!vis[i]){
                vis[i] = 1;
                q.push(i);
                p.push(pf);
                d.push(df + 1);
            }
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    memset(ped,-1,sizeof(ped));
    memset(dist0,-1,sizeof(dist0));
    memset(dist1,-1,sizeof(dist1));
    memset(peri0,-1,sizeof(peri0));
    memset(peri1,-1,sizeof(peri1));
    memset(low,0x3f,sizeof(low));
    make_graph(N,M,R);
    for (int i=0; i<2*N; i++) {
        deg[i]++;
        deg[nxt[i]]++;
    }
    for (int i=0; i<2*N; i++) {
        if(deg[i] == 1){
            q.push(i);
        }
    }
    while (!q.empty()) {
        int qf = q.front();
        q.pop();
        deg[qf]--;
        deg[nxt[qf]]--;
        if(deg[nxt[qf]] == 1){
            q.push(nxt[qf]);
        }
    }
    for (int i=0; i<2*N; i++) {
        graph1[nxt[i]].push_back(i);
        if(deg[i]){
            int pos = i;
            ls.clear();
            while (deg[pos]) {
                deg[pos] = 0;
                ls.push_back(pos);
                pos = nxt[pos];
            }
            for (auto &i : ls){
                ped[i] = (int)ls.size();
            }
        }
    }
    solve(2*P,dist0,peri0);
    solve(2*P+1,dist1,peri1);
    for (int i=0; i<Q; i++) {
        int cnt = 0;
        for (int j=0; j<N; j++) {
            if(dist0[j] != -1){
                if(peri0[j] == -1){
                    if(dist0[j] == G[i]){
                        cnt++; continue;
                    }
                }
                else{
                    if(dist0[j] <= G[i] && (G[i] - dist0[j]) % peri0[j] == 0){
                        cnt++; continue;
                    }
                }
            }
            if(dist1[j] != -1){
                if(peri1[j] == -1){
                    if(dist1[j] == G[i]){
                        cnt++; continue;
                    }
                }
                else{
                    if(dist1[j] <= G[i] && (G[i] - dist1[j]) %peri1[j] == 0){
                        cnt++; continue;
                    }
                }
            }
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15452 KB Output is correct
2 Correct 16 ms 15480 KB Output is correct
3 Correct 17 ms 15392 KB Output is correct
4 Correct 16 ms 15324 KB Output is correct
5 Correct 16 ms 15352 KB Output is correct
6 Correct 17 ms 15480 KB Output is correct
7 Correct 16 ms 15352 KB Output is correct
8 Correct 19 ms 15352 KB Output is correct
9 Correct 18 ms 15608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15452 KB Output is correct
2 Correct 16 ms 15480 KB Output is correct
3 Correct 17 ms 15392 KB Output is correct
4 Correct 16 ms 15324 KB Output is correct
5 Correct 16 ms 15352 KB Output is correct
6 Correct 17 ms 15480 KB Output is correct
7 Correct 16 ms 15352 KB Output is correct
8 Correct 19 ms 15352 KB Output is correct
9 Correct 18 ms 15608 KB Output is correct
10 Correct 15 ms 15324 KB Output is correct
11 Correct 30 ms 17672 KB Output is correct
12 Correct 53 ms 19464 KB Output is correct
13 Correct 69 ms 25932 KB Output is correct
14 Correct 179 ms 28388 KB Output is correct
15 Correct 228 ms 28768 KB Output is correct
16 Correct 167 ms 25476 KB Output is correct
17 Correct 161 ms 24728 KB Output is correct
18 Correct 52 ms 19320 KB Output is correct
19 Correct 177 ms 28280 KB Output is correct
20 Correct 216 ms 28692 KB Output is correct
21 Correct 168 ms 25428 KB Output is correct
22 Correct 156 ms 24596 KB Output is correct
23 Correct 167 ms 29492 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15452 KB Output is correct
2 Correct 16 ms 15480 KB Output is correct
3 Correct 17 ms 15392 KB Output is correct
4 Correct 16 ms 15324 KB Output is correct
5 Correct 16 ms 15352 KB Output is correct
6 Correct 17 ms 15480 KB Output is correct
7 Correct 16 ms 15352 KB Output is correct
8 Correct 19 ms 15352 KB Output is correct
9 Correct 18 ms 15608 KB Output is correct
10 Correct 15 ms 15324 KB Output is correct
11 Correct 30 ms 17672 KB Output is correct
12 Correct 53 ms 19464 KB Output is correct
13 Correct 69 ms 25932 KB Output is correct
14 Correct 179 ms 28388 KB Output is correct
15 Correct 228 ms 28768 KB Output is correct
16 Correct 167 ms 25476 KB Output is correct
17 Correct 161 ms 24728 KB Output is correct
18 Correct 52 ms 19320 KB Output is correct
19 Correct 177 ms 28280 KB Output is correct
20 Correct 216 ms 28692 KB Output is correct
21 Correct 168 ms 25428 KB Output is correct
22 Correct 156 ms 24596 KB Output is correct
23 Correct 167 ms 29492 KB Output is correct
24 Correct 17 ms 15324 KB Output is correct
25 Correct 110 ms 17680 KB Output is correct
26 Correct 152 ms 19420 KB Output is correct
27 Correct 1497 ms 26056 KB Output is correct
28 Correct 1259 ms 28360 KB Output is correct
29 Correct 1844 ms 28748 KB Output is correct
30 Correct 975 ms 25488 KB Output is correct
31 Correct 891 ms 24788 KB Output is correct
32 Correct 166 ms 19984 KB Output is correct
33 Correct 1267 ms 29656 KB Output is correct
34 Correct 1731 ms 30092 KB Output is correct
35 Correct 974 ms 26588 KB Output is correct
36 Correct 1440 ms 25836 KB Output is correct
37 Correct 898 ms 30912 KB Output is correct
38 Correct 2525 ms 33580 KB Output is correct