oj.uz

답안 #136625

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136625 2019-07-25T22:18:07 Z jovan_b 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 236 ms 122900 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-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.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47608 KB Output is correct
2 Correct 45 ms 47480 KB Output is correct
3 Correct 44 ms 47480 KB Output is correct
4 Correct 55 ms 47352 KB Output is correct
5 Correct 44 ms 47352 KB Output is correct
6 Correct 46 ms 47816 KB Output is correct
7 Correct 55 ms 47352 KB Output is correct
8 Correct 60 ms 47452 KB Output is correct
9 Correct 47 ms 47708 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47608 KB Output is correct
2 Correct 45 ms 47480 KB Output is correct
3 Correct 44 ms 47480 KB Output is correct
4 Correct 55 ms 47352 KB Output is correct
5 Correct 44 ms 47352 KB Output is correct
6 Correct 46 ms 47816 KB Output is correct
7 Correct 55 ms 47352 KB Output is correct
8 Correct 60 ms 47452 KB Output is correct
9 Correct 47 ms 47708 KB Output is correct
10 Correct 48 ms 47300 KB Output is correct
11 Correct 60 ms 49944 KB Output is correct
12 Correct 82 ms 51560 KB Output is correct
13 Correct 129 ms 85724 KB Output is correct
14 Runtime error 236 ms 122900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47608 KB Output is correct
2 Correct 45 ms 47480 KB Output is correct
3 Correct 44 ms 47480 KB Output is correct
4 Correct 55 ms 47352 KB Output is correct
5 Correct 44 ms 47352 KB Output is correct
6 Correct 46 ms 47816 KB Output is correct
7 Correct 55 ms 47352 KB Output is correct
8 Correct 60 ms 47452 KB Output is correct
9 Correct 47 ms 47708 KB Output is correct
10 Correct 48 ms 47300 KB Output is correct
11 Correct 60 ms 49944 KB Output is correct
12 Correct 82 ms 51560 KB Output is correct
13 Correct 129 ms 85724 KB Output is correct
14 Runtime error 236 ms 122900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -