Submission #442463

#	Time	Username	Problem	Language	Result	Execution time	Memory
442463		JovanB	Tropical Garden (IOI11_garden)	C++17	100 / 100	3267 ms	100832 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][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<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=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){
                    resenje[i] = 1;
                }
            }
        }
        for(int i=0; i<n; i++){
            cnt += resenje[i];
        }
        answer(cnt);
    }
    return;
}

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