Submission #136625

#	Time	Username	Problem	Language	Result	Execution time	Memory
136625		jovan_b	Tropical Garden (IOI11_garden)	C++17	49 / 100	236 ms	122900 KiB

garden

#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-k] = 1;
            }
            else if(cycle_size[p]){
                if(k > depth[i] && (k-depth[i])%cycle_size[p] == 0){
                    resenje[i-k] = 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
*/

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31