제출 #297160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297160		Kastanda	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	100 / 100	206 ms	45984 KiB

garden

/*
    Take me to church
    I'll worship like a dog at the shrine of your lies
    I'll tell you my sins and you can sharpen your knife
    Offer me that deathless death
    Good God, let me give you my life
*/
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define x first
#define y second
using namespace std;
const int N = 150004, MXQ = 2002;
int n, m, q, p, MN[N], Q[MXQ], RS[MXQ];
int F[N * 2], D[N * 2], qu[N * 2];
vector < pair < int , int > > vec[N * 2], Adj[N];
vector < int > ps[N * 2], Adt[N * 2];
map < int , int > MP;
inline void Solve(int dt)
{
    int l = 0, r = 0;
    memset(D, -1, sizeof(D));
    for (int u : Adt[dt])
        D[u] = 1, qu[r ++] = u;
    while (r - l)
    {
        int v = qu[l ++];
        for (int u : Adt[v])
            if (D[u] == -1)
                D[u] = D[v] + 1, qu[r ++] = u;
    }
    if (D[dt] == -1)
    {
        for (int i = 0; i < n; i ++)
            if (D[i << 1] != -1)
                MP[D[i << 1]] ++;
        return ;
    }
    for (int i = 0; i < q; i ++)
        vec[Q[i] % D[dt]].push_back({Q[i], i});
    for (int i = 0; i < D[dt]; i ++)
        sort(vec[i].begin(), vec[i].end()), ps[i].resize(vec[i].size());
    for (int i = 0; i < n; i ++)
    {
        if (D[i << 1] == -1)
            continue;
        int d = D[i << 1], r = d % D[dt];
        int lb = lower_bound(vec[r].begin(), vec[r].end(), pair < int , int > {d, -1}) - vec[r].begin();
        if (lb < vec[r].size())
            ps[r][lb] ++;
    }
    for (int i = 0; i < D[dt]; i ++)
    {
        for (int j = 0; j < (int)ps[i].size() - 1; j ++)
            ps[i][j + 1] += ps[i][j];
        for (int j = 0; j < (int)vec[i].size(); j ++)
            RS[vec[i][j].second] += ps[i][j];
        vec[i].clear();
        ps[i].clear();
    }
    return ;
}
void count_routes(int _n, int _m, int _p, int _E[N][2], int _q, int _Q[MXQ])
//int main()
{
    n = _n; m = _m; p = _p; q = _q;
    //cin >> n >> m >> p >> q;
    for (int i = 0; i < q; i ++)
        Q[i] = _Q[i];
        //cin >> Q[i];
    memset(MN, 63, sizeof(MN));
    for (int i = 0; i < m; i ++)
    {
        int v = _E[i][0], u = _E[i][1];
        //int v, u;
        //cin >> v >> u;
        Adj[v].push_back({i, u});
        Adj[u].push_back({i, v});
        MN[v] = min(MN[v], i);
        MN[u] = min(MN[u], i);
    }
    for (int i = 0; i < n; i ++)
    {
        F[i << 1] = F[i << 1 | 1] = -1;
        sort(Adj[i].begin(), Adj[i].end());
        if (Adj[i].size() == 0)
            continue;
        int u = Adj[i][0].y;
        if (MN[u] < Adj[i][0].x || Adj[u].size() == 1)
            F[i << 1] = u << 1;
        else
            F[i << 1] = u << 1 | 1;
        if (Adj[i].size() == 1)
            continue;
        u = Adj[i][1].y;
        if (MN[u] < Adj[i][1].x || Adj[u].size() == 1)
            F[i << 1 | 1] = u << 1;
        else
            F[i << 1 | 1] = u << 1 | 1;
    }
    for (int i = 0; i < n + n; i ++)
        if (F[i] != -1)
            Adt[F[i]].push_back(i);

    /*for (int i = 0; i < n + n; i ++)
        printf("%d ", F[i]);
    printf("\n");*/

    Solve(p << 1);
    Solve(p << 1 | 1);
    for (int i = 0; i < q; i ++)
    {
        RS[i] += MP[Q[i]];
        answer(RS[i]);
        //printf("%d ", RS[i]);
    }
    return ;
    //return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void Solve(int)':
garden.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if (lb < vec[r].size())
      |             ~~~^~~~~~~~~~~~~~~

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