oj.uz

Submission #121113

# Submission time Handle Problem Language Result Execution time Memory
121113 2019-06-26T06:32:45 Z 송준혁(#2942) Tropical Garden (IOI11_garden) C++14
0 / 100
 15 ms 13432 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define INF (1<<30)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, P, Q, C1, C2;
int O[202020], D1[202020], D2[202020];
int cnt1[1010101], cnt2[1010101];
vector<pii> G[202020];
vector<int> radj[303030];
int adj[303030];
bool visit[303030];

void dfs1(int u, int d){
    if (visit[u]) return;
    visit[u] = true;
    if (u < N) cnt1[d]++;
    for (int v : radj[u]) dfs1(v, d+1);
}

void dfs2(int u, int d){
    if (visit[u]) return;
    visit[u] = true;
    if (u < N) cnt2[d]++;
    for (int v : radj[u]) dfs2(v, d+1);
}

int cyc1(int u, int d){
    if (visit[u]) return -1;
    if (u == P) return d;
    visit[u] = true;
    return cyc1(adj[u], d+1);
}

int cyc2(int u, int d){
    if (visit[u]) return -1;
    if (u == P+N) return d;
    visit[u] = true;
    return cyc2(adj[u], d+1);
}

void count_routes(int n, int m, int p, int R[][2], int q, int d[]){
    N=n, M=m, P=p, Q=q;
    for (int i=0; i<M; i++){
        G[R[i][0]].push_back(pii(i, R[i][1]));
        G[R[i][1]].push_back(pii(i, R[i][0]));
    }
    for (int i=0; i<N; i++){
        int Min=INF;
        for (pii j : G[i]) if (j.first < Min) Min = j.first, O[i] = j.second;
    }
    for (int i=0; i<N; i++){
        if (O[O[i]] != i) {
            radj[O[i]].push_back(i);
            adj[i] = O[i];
        }
        else {
            radj[O[i]+N].push_back(i);
            adj[i] = O[i]+N;
        }
        int Min=INF, u=-1;
        for (pii j : G[i]) if (j.first < Min) {
            if (j.second == O[i]) continue;
            Min = j.first, u = j.second;
        }
        if (u != -1){
            if (O[u] == i) {
                radj[u+N].push_back(i+N);
                adj[i+N] = u+N;
            }
            else {
                radj[u].push_back(i+N);
                adj[i+N] = u;
            }
        }
        else {
            radj[O[i]+N].push_back(i+N);
            adj[i+N] = O[i]+N;
        }
    }
    memset(D1, -1, sizeof D1);
    dfs1(P, 0);
    memset(visit, false, sizeof visit);
    dfs2(P+N, 0);
    for (int i=1; i<=N; i++){
        if (D1[i] != -1) cnt1[D1[i]]++;
        if (D2[i] != -1) cnt2[D2[i]]++;
    }
    memset(visit, false, sizeof visit);
    C1 = cyc1(adj[P], 1);
    memset(visit, false, sizeof visit);
    C2 = cyc2(adj[P+N], 1);
    if (C1 != -1) for (int i=C1; i<=6*N; i++) cnt1[i] += cnt1[i-C1];
    if (C2 != -1) for (int i=C2; i<=6*N; i++) cnt2[i] += cnt2[i-C2];
    int t1=0, t2=0;
    if (C1 != -1) while (t1 <= 2*N) t1 += C1;
    if (C2 != -1) while (t2 <= 2*N) t2 += C2;
    for (int i=0; i<Q; i++){
        if (d[i] <= 2*N) answer(cnt1[d[i]] + cnt2[d[i]]);
        else{
            int ans=0;
            if (C1 != -1) ans += cnt1[t1+d[i]%C1];
            if (C2 != -1) ans += cnt1[t2+d[i]%C2];
            answer(ans);
        }
    }
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 13432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 13432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 13432 KB Output isn't correct
2 Halted 0 ms 0 KB -