oj.uz

답안 #14810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
14810 2015-06-27T13:57:40 Z gs14004 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 14 ms 13052 KB 
#include "garden.h"
#include "gardenlib.h"
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;

vector<pi> graph0[150005];
vector<int> graph1[300005];
vector<int> proc;

int nxt[300005];
int low[150005];
int periods[300005];
int deg[300005];
int n, qcnt;
int *g;

int ret[2005];

queue<int> q, p, d;
bool vis[300005];

void get_periods(){
    for (int i=0; i<2*n; i++) {
        if(deg[i] == 1){
            q.push(i);
        }
    }
    while (!q.empty()) {
        int qf = q.front();
        q.pop();
        deg[qf] = 0;
        for (auto &i : graph1[qf]){
            deg[i]--;
            if(deg[i] == 1){
                q.push(i);
            }
        }
        if(deg[nxt[qf]] == 1){
            q.push(nxt[qf]);
        }
    }
    for (int i=0; i<2*n; i++) {
        if(deg[i] != 0){
            proc.clear();
            q.push(i);
            int cnt = 0;
            while (!q.empty()) {
                int qf = q.front();
                q.pop();
                deg[qf] = 0;
                cnt++;
                proc.push_back(qf);
                for (auto &i : graph1[qf]){
                    if(deg[i] != 0){
                        deg[i] = 0;
                        q.push(i);
                    }
                }
                if(deg[nxt[qf]] != 0){
                    deg[nxt[qf]] = 0;
                    q.push(nxt[qf]);
                }
            }
            for (auto &i : proc){
                periods[i] = cnt;
            }
        }
    }
   // for (int i=0; i<2*n; i++) {
     //   printf("%d %d\n",i, periods[i]);
    //}
}

void solve(int st){ // st 점에서 G[i] 번 방문해서 도달하는 점의 개수 추가
    memset(vis,0,sizeof(vis));
    q.push(st);
    p.push(-1);
    d.push(0);
    vis[st] = 1;
    while (!q.empty()) {
        int qf = q.front(), pf = p.front(), df = d.front();
        q.pop(), p.pop(), d.pop();
        pf = max(pf, periods[qf]);
        if(qf % 2 == 0){
            for (int i=0; i<qcnt; i++) {
                if(pf == -1){
                    if(df == g[i]){
                    //    printf("%d %d\n",i,qf/2);
                        ret[i]++;
                    }
                }
                else{
                    if(df <= g[i] && g[i] % pf == df % pf){
                    //    printf("%d %d\n",i,qf/2);
                        ret[i]++;
                    }
                }
            }
        }
        for (auto &i : graph1[qf]){
            if(vis[i]) continue;
            vis[i] = 1;
            q.push(i);
            p.push(pf);
            d.push(df + 1);
        }
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n = N, qcnt = Q, g = G;
    memset(periods,-1,sizeof(periods));
    memset(low,0x3f,sizeof(low));
    for (int i=0; i<M; i++) {
        for (int j=0; j<2; j++) {
            low[R[i][j]] = min(low[R[i][j]],i);
        }
        graph0[R[i][0]].push_back(pi(R[i][1],i));
        graph0[R[i][1]].push_back(pi(R[i][0],i));
    }
    for (int i=0; i<N; i++) {
        if(low[graph0[i][0].first] == graph0[i][0].second){
            nxt[2*i] = graph0[i][0].first * 2 + 1;
        }
        else{
            nxt[2*i] = graph0[i][0].first * 2;
        }
        if(graph0[i].size() == 1){
            nxt[2*i+1] = nxt[2*i];
        }
        else{
            if(low[graph0[i][1].first] == graph0[i][1].second){
                nxt[2*i+1] = graph0[i][1].first * 2 + 1;
            }
            else{
                nxt[2*i+1] = graph0[i][1].first * 2;
            }
        }
    }
    for (int i=0; i<2*N; i++){
      //  printf("%d %d\n",i,nxt[i]);
        graph1[nxt[i]].push_back(i);
        deg[i]++;
        deg[nxt[i]]++;
    }
    get_periods();
    solve(2*P);
    solve(2*P+1);
    for (int i=0; i<Q; i++) {
        answer(ret[i]);
    }
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 13052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 13052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 13052 KB Output isn't correct
2 Halted 0 ms 0 KB -