oj.uz

답안 #136630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136630 2019-07-25T23:01:12 Z jovan_b 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 46 ms 47676 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

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=n; i<2*n; i++){
            if(dgraf[i-n].size() != 1){
                continue;
            }
            if(depth[i][0] == INF) 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<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
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 47676 KB Output is correct
2 Correct 44 ms 47528 KB Output is correct
3 Incorrect 44 ms 47580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 47676 KB Output is correct
2 Correct 44 ms 47528 KB Output is correct
3 Incorrect 44 ms 47580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 47676 KB Output is correct
2 Correct 44 ms 47528 KB Output is correct
3 Incorrect 44 ms 47580 KB Output isn't correct
4 Halted 0 ms 0 KB -