Submission #44887

#	Time	Username	Problem	Language	Result	Execution time	Memory
44887		RayaBurong25_1	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2075 ms	14292 KiB

bitaro

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1000000007
std::vector<int> AdjList[100005];
int Seg[400005];
typedef struct query query;
struct query
{
    int i, T;
    std::vector<int> Y;
};
std::vector<query> Queries;
int compare(query a, query b)
{
    return (a.T < b.T);
}
int Ans[100005];
int Out[100005];
std::vector<int> Topo;
int Pos[100005];
int Longest[100005];
int Vis[100005], cnt;
int N;
int max(int a, int b)
{
    return (a > b)?a:b;
}
void makeTree(int s, int e, int cell)
{
    if (s == e)
    {
        Seg[cell] = Longest[s];
        return;
    }
    int m = (s + e)/2;
    makeTree(s, m, 2*cell + 1);
    makeTree(m + 1, e, 2*cell + 2);
    Seg[cell] = max(Seg[2*cell + 1], Seg[2*cell + 2]);
}
void explore(int pos)
{
    // printf("explore %d (%d): ", pos, Topo[pos]);
    cnt++;
    Longest[Topo[pos]] = 0;
    Vis[Topo[pos]] = cnt;
    int i, u;
    while (pos < N)
    {
        u = Topo[pos];
        // printf("u%d\n", u);
        if (Vis[u] < cnt)
        {
            Vis[u] = cnt;
            Longest[u] = -INF;
        }
        for (i = 0; i < AdjList[u].size(); i++)
        {
            // printf("  v%d\n", AdjList[u][i]);
            if (Vis[AdjList[u][i]] < cnt)
            {
                Vis[AdjList[u][i]] = cnt;
                Longest[AdjList[u][i]] = Longest[u] + 1;
            }
            else if (Longest[u] + 1 > Longest[AdjList[u][i]])
            {
                Longest[AdjList[u][i]] = Longest[u] + 1;
            }
        }
        pos++;
    }
    for (i = 1; i <= N; i++)
    {
        if (Vis[i] < cnt)
        {
            Vis[i] = cnt;
            Longest[i] = -INF;
        }
        // printf("%d ", Longest[i]);
    }
    // printf("\n");
    makeTree(1, N, 0);
}
void update(int p, int v, int s, int e, int cell)
{
    if (s == e)
    {
        Seg[cell] = v;
        return;
    }
    int m = (s + e)/2;
    if (p <= m)
        update(p, v, s, m, 2*cell + 1);
    else
        update(p, v, m + 1, e, 2*cell + 2);
    Seg[cell] = max(Seg[2*cell + 1], Seg[2*cell + 2]);
}
int answer(int q)
{
    int i;
    for (i = 0; i < Queries[q].Y.size(); i++)
        update(Queries[q].Y[i], -INF, 1, N, 0);
    int r = Seg[0];
    for (i = 0; i < Queries[q].Y.size(); i++)
        update(Queries[q].Y[i], Longest[Queries[q].Y[i]], 1, N, 0);
    if (r < 0)
        return -1;
    else
        return r;
}
int main()
{
    int M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    int i, u, v;
    for (i = 0; i < M; i++)
    {
        scanf("%d %d", &u, &v);
        AdjList[v].push_back(u);
        Out[u]++;
    }
    std::queue<int> Qu;
    for (i = 1; i <= N; i++)
        if (Out[i] == 0)
            Qu.push(i);
    while (!Qu.empty())
    {
        u = Qu.front();
        Qu.pop();
        Pos[u] = Topo.size();
        Topo.push_back(u);

        for (i = 0; i < AdjList[u].size(); i++)
        {
            Out[AdjList[u][i]]--;
            if (Out[AdjList[u][i]] == 0)
                Qu.push(AdjList[u][i]);
        }
    }
    // printf("Topo: ");
    // for (i = 0; i < Topo.size(); i++)
        // printf("%d ", Topo[i]);
    // printf("\n");
    int T, Y, j, y;
    query p;
    for (i = 0; i < Q; i++)
    {
        scanf("%d %d", &T, &Y);
        p.i = i;
        p.T = T;
        p.Y.clear();
        for (j = 0; j < Y; j++)
        {
            scanf("%d", &y);
            p.Y.push_back(y);
        }
        Queries.push_back(p);
    }
    std::sort(Queries.begin(), Queries.end(), compare);
    for (i = 0; i < Q; i++)
    {
        if (i == 0 || Queries[i].T != Queries[i - 1].T)
        {
            explore(Pos[Queries[i].T]);
        }
        Ans[Queries[i].i] = answer(i);
    }
    for (i = 0; i < Q; i++)
        printf("%d\n", Ans[i]);
}

Compilation message (stderr)

bitaro.cpp: In function 'void explore(int)':
bitaro.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < AdjList[u].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int answer(int)':
bitaro.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < Queries[q].Y.size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < Queries[q].Y.size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:134:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < AdjList[u].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &T, &Y);
         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:155:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &y);
             ~~~~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86