oj.uz

Submission #136626

# Submission time Handle Problem Language Result Execution time Memory
136626 2019-07-25T22:29:25 Z jovan_b Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 85932 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];
int cycle_size[1000005];
bool visited[1000005];

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

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++){
        //cout << i << "<-" << parent[i] << "\n";
        graf[parent[i]].push_back(i);
    }
    //return;
    for(int query=0; query<q; query++){
        int k = G[query];
        int cnt = 0;
        for(int i=0; i<2*n; i++){
            visited[i] = 0;
            depth[i] = -1;
            resenje[i] = 0;
        }
        depth[p] = 0;
        dfs(p);
        for(int i=0; i<n; i++){
            if(depth[i] == -1) continue;
            //cout << i << " depth " << depth[i] << endl;
            if(depth[i] == k){
                resenje[i] = 1;
            }
            else if(cycle_size[p]){
                if(k > depth[i] && (k-depth[i])%cycle_size[p] == 0){
                    resenje[i] = 1;
                }
            }
        }
        for(int i=n; i<2*n; i++){
            if(dgraf[i-n].size() != 1){
                //cout << n-i << endl;
                continue;
            }
            if(depth[i] == -1) continue;
            if(depth[i] == k){
                resenje[i-n] = 1;
            }
            else if(cycle_size[p]){
                if(k > depth[i] && (k-depth[i])%cycle_size[p] == 0){
                    resenje[i-n] = 1;
                }
            }
        }
        /*for(int i=0; i<n; i++){
            cout << i << " resenje " << resenje[i] << endl;
        }*/
        for(int i=0; i<2*n; i++){
            visited[i] = 0;
            depth[i] = -1;
        }
        depth[p+n] = 0;
        dfs(p+n);
        for(int i=0; i<n; i++){
            //cout << i << " depth " << depth[i] << endl;
            if(depth[i] == -1) continue;
            if(depth[i] == k){
                resenje[i] = 1;
            }
            else if(cycle_size[p+n]){
                if(k > depth[i] && (k-depth[i])%cycle_size[p+n] == 0){
                    resenje[i] = 1;
                }
            }
        }
        for(int i=n; i<2*n; i++){
            if(dgraf[i-n].size() != 1){
                //cout << n-i << endl;
                continue;
            }
            if(depth[i] == -1) continue;
            if(depth[i] == k){
                resenje[i-n] = 1;
            }
            else if(cycle_size[p+n]){
                //cout << depth[i] << " fg " << cycle_size[i] << endl;
                if(k > depth[i] && (k-depth[i])%cycle_size[p+n] == 0){
                    resenje[i-n] = 1;
                }
            }
        }
        for(int i=0; i<n; i++){
            //cout << i << " resenje " << resenje[i] << endl;
            cnt += resenje[i];
        }
        //cout << cnt << " je resenje\n";
        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 52 ms 47824 KB Output is correct
2 Correct 45 ms 47540 KB Output is correct
3 Correct 45 ms 47476 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 44 ms 47272 KB Output is correct
6 Correct 46 ms 47736 KB Output is correct
7 Correct 44 ms 47324 KB Output is correct
8 Correct 46 ms 47452 KB Output is correct
9 Correct 48 ms 47644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47824 KB Output is correct
2 Correct 45 ms 47540 KB Output is correct
3 Correct 45 ms 47476 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 44 ms 47272 KB Output is correct
6 Correct 46 ms 47736 KB Output is correct
7 Correct 44 ms 47324 KB Output is correct
8 Correct 46 ms 47452 KB Output is correct
9 Correct 48 ms 47644 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 60 ms 49964 KB Output is correct
12 Correct 76 ms 51692 KB Output is correct
13 Correct 156 ms 85776 KB Output is correct
14 Correct 249 ms 60832 KB Output is correct
15 Correct 219 ms 61160 KB Output is correct
16 Correct 176 ms 58268 KB Output is correct
17 Correct 162 ms 56796 KB Output is correct
18 Correct 82 ms 51548 KB Output is correct
19 Correct 182 ms 60940 KB Output is correct
20 Correct 227 ms 61120 KB Output is correct
21 Correct 179 ms 58052 KB Output is correct
22 Correct 160 ms 56920 KB Output is correct
23 Correct 174 ms 62204 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47824 KB Output is correct
2 Correct 45 ms 47540 KB Output is correct
3 Correct 45 ms 47476 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 44 ms 47272 KB Output is correct
6 Correct 46 ms 47736 KB Output is correct
7 Correct 44 ms 47324 KB Output is correct
8 Correct 46 ms 47452 KB Output is correct
9 Correct 48 ms 47644 KB Output is correct
10 Correct 44 ms 47352 KB Output is correct
11 Correct 60 ms 49964 KB Output is correct
12 Correct 76 ms 51692 KB Output is correct
13 Correct 156 ms 85776 KB Output is correct
14 Correct 249 ms 60832 KB Output is correct
15 Correct 219 ms 61160 KB Output is correct
16 Correct 176 ms 58268 KB Output is correct
17 Correct 162 ms 56796 KB Output is correct
18 Correct 82 ms 51548 KB Output is correct
19 Correct 182 ms 60940 KB Output is correct
20 Correct 227 ms 61120 KB Output is correct
21 Correct 179 ms 58052 KB Output is correct
22 Correct 160 ms 56920 KB Output is correct
23 Correct 174 ms 62204 KB Output is correct
24 Correct 50 ms 47324 KB Output is correct
25 Correct 1014 ms 49988 KB Output is correct
26 Correct 1504 ms 51588 KB Output is correct
27 Execution timed out 5055 ms 85932 KB Time limit exceeded
28 Halted 0 ms 0 KB -