oj.uz

Submission #136636

# Submission time Handle Problem Language Result Execution time Memory
136636 2019-07-25T23:10:58 Z jovan_b Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 92292 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

vector <pair <int, int>> dgraf[1000005];
int parent[1000005];
vector <int> graf[1000005];

bool resenje[1000005];

bool cmp(pair <int, int> a, pair <int, int> b){
    return a.second < b.second;
}

int n, m, p, q;
int depth[1000005][2];
int cycle_size[1000005];
bool visited[1000005][2];

void dfs(int v, int koji){
    visited[v][koji] = 1;
    for(auto c : graf[v]){
        if(visited[c][koji]){
            int x = v;
            queue <int> q;
            while(x != c){
                q.push(x);
                x = parent[x];
                if(x == c) break;
            }
            q.push(c);
            int g = q.size();
            while(!q.empty()){
                cycle_size[q.front()] = g;
                q.pop();
            }
        }
        else{
            depth[c][koji] = depth[v][koji] + 1;
            dfs(c, koji);
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
    n = N, m = M, p = P, q = Q;
    for(int i=0; i<m; i++){
        dgraf[R[i][0]].push_back({R[i][1], i});
        dgraf[R[i][1]].push_back({R[i][0], i});
    }
    for(int i=0; i<n; i++){
        sort(dgraf[i].begin(), dgraf[i].end(), cmp);
    }
    for(int i=0; i<n; i++){
        if(dgraf[i].size() == 1){
            if(dgraf[dgraf[i][0].first][0].first == i){
                parent[i] = dgraf[i][0].first + n;
                parent[i+n] = dgraf[i][0].first + n;
            }
            else{
                parent[i] = dgraf[i][0].first;
                parent[i+n] = dgraf[i][0].first;
            }
        }
        else{
            if(dgraf[dgraf[i][0].first][0].first == i) parent[i] = dgraf[i][0].first + n;
            else parent[i] = dgraf[i][0].first;
            if(dgraf[dgraf[i][1].first][0].first == i) parent[i+n] = dgraf[i][1].first + n;
            else parent[i+n] = dgraf[i][1].first;
        }
    }
    for(int i=0; i<2*n; i++){
        graf[parent[i]].push_back(i);
    }
    for(int i=0; i<2*n; i++){
        depth[i][0] = depth[i][1] = -1;
    }
    /*depth[p][0] = 0;
    dfs(p, 0);
    depth[p+n][1] = 0;
    dfs(p+n, 1);*/
    for(int query=0; query<q; query++){
        int k = G[query];
        int cnt = 0;
        for(int i=0; i<n; i++) resenje[i] = 0;
        for(int i=0; i<2*n; i++){
            visited[i][0] = 0;
            depth[i][0] = -1;
            resenje[i] = 0;
        }
        depth[p][0] = 0;
        dfs(p, 0);
        for(int i=0; i<n; i++){
            if(depth[i][0] == -1) continue;
            if(depth[i][0] == k){
                resenje[i] = 1;
            }
            else if(cycle_size[p]){
                if(k > depth[i][0] && (k-depth[i][0])%cycle_size[p] == 0){
                    resenje[i] = 1;
                    //cout << i << " e1 " << endl;
                }
            }
        }
        for(int i=n; i<2*n; i++){
            if(dgraf[i-n].size() != 1){
                continue;
            }
            if(depth[i][0] == -1) continue;
            if(depth[i][0] == k){
                resenje[i-n] = 1;
            }
            else if(cycle_size[p]){
                if(k > depth[i][0] && (k-depth[i][0])%cycle_size[p] == 0){
                    resenje[i-n] = 1;
                    //cout << i << " e2 " << endl;
                }
            }
        }
        /// drugi
        for(int i=0; i<2*n; i++){
            visited[i][1] = 0;
            depth[i][1] = -1;
        }
        depth[p+n][1] = 0;
        dfs(p+n, 1);
        for(int i=0; i<n; i++){
            if(depth[i][1] == -1) continue;
            if(depth[i][1] == k){
                resenje[i] = 1;
            }
            else if(cycle_size[p+n]){
                if(k > depth[i][1] && (k-depth[i][1])%cycle_size[p+n] == 0){
                    //cout << i << " e3 " << endl;
                    resenje[i] = 1;
                }
            }
        }
        for(int i=n; i<2*n; i++){
            if(dgraf[i-n].size() != 1){
                continue;
            }
            if(depth[i][1] == -1) continue;
            if(depth[i][1] == k){
                resenje[i-n] = 1;
            }
            else if(cycle_size[p+n]){
                if(k > depth[i][1] && (k-depth[i][1])%cycle_size[p+n] == 0){
                    resenje[i-n] = 1;
                    //cout << i << " e4 " << endl;
                }
            }
        }
        for(int i=0; i<n; i++){
            cnt += resenje[i];
        }
        answer(cnt);
    }
    return;
}
/*
2
1 0
0 1
5
1 2 3 4 5
sdgfhsdfgdfgds
*/

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47708 KB Output is correct
2 Correct 44 ms 47464 KB Output is correct
3 Correct 44 ms 47580 KB Output is correct
4 Correct 45 ms 47376 KB Output is correct
5 Correct 43 ms 47336 KB Output is correct
6 Correct 45 ms 47852 KB Output is correct
7 Correct 44 ms 47404 KB Output is correct
8 Correct 45 ms 47444 KB Output is correct
9 Correct 47 ms 47660 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47708 KB Output is correct
2 Correct 44 ms 47464 KB Output is correct
3 Correct 44 ms 47580 KB Output is correct
4 Correct 45 ms 47376 KB Output is correct
5 Correct 43 ms 47336 KB Output is correct
6 Correct 45 ms 47852 KB Output is correct
7 Correct 44 ms 47404 KB Output is correct
8 Correct 45 ms 47444 KB Output is correct
9 Correct 47 ms 47660 KB Output is correct
10 Correct 44 ms 47276 KB Output is correct
11 Correct 60 ms 50228 KB Output is correct
12 Correct 82 ms 51872 KB Output is correct
13 Correct 137 ms 91916 KB Output is correct
14 Correct 184 ms 62180 KB Output is correct
15 Correct 238 ms 62404 KB Output is correct
16 Correct 192 ms 59364 KB Output is correct
17 Correct 169 ms 57656 KB Output is correct
18 Correct 92 ms 51840 KB Output is correct
19 Correct 188 ms 62056 KB Output is correct
20 Correct 235 ms 62436 KB Output is correct
21 Correct 185 ms 59060 KB Output is correct
22 Correct 166 ms 57624 KB Output is correct
23 Correct 188 ms 63708 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47708 KB Output is correct
2 Correct 44 ms 47464 KB Output is correct
3 Correct 44 ms 47580 KB Output is correct
4 Correct 45 ms 47376 KB Output is correct
5 Correct 43 ms 47336 KB Output is correct
6 Correct 45 ms 47852 KB Output is correct
7 Correct 44 ms 47404 KB Output is correct
8 Correct 45 ms 47444 KB Output is correct
9 Correct 47 ms 47660 KB Output is correct
10 Correct 44 ms 47276 KB Output is correct
11 Correct 60 ms 50228 KB Output is correct
12 Correct 82 ms 51872 KB Output is correct
13 Correct 137 ms 91916 KB Output is correct
14 Correct 184 ms 62180 KB Output is correct
15 Correct 238 ms 62404 KB Output is correct
16 Correct 192 ms 59364 KB Output is correct
17 Correct 169 ms 57656 KB Output is correct
18 Correct 92 ms 51840 KB Output is correct
19 Correct 188 ms 62056 KB Output is correct
20 Correct 235 ms 62436 KB Output is correct
21 Correct 185 ms 59060 KB Output is correct
22 Correct 166 ms 57624 KB Output is correct
23 Correct 188 ms 63708 KB Output is correct
24 Correct 50 ms 47384 KB Output is correct
25 Correct 1175 ms 50296 KB Output is correct
26 Correct 1780 ms 51948 KB Output is correct
27 Execution timed out 5011 ms 92292 KB Time limit exceeded
28 Halted 0 ms 0 KB -