Submission #238331

#	Time	Username	Problem	Language	Result	Execution time	Memory
238331		Charis02	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1806 ms	171128 KiB

bitaro

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<unordered_set>
#include<algorithm>
#define pi pair < int,int >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004

using namespace std;

int n,m,q;
vector < pi > longest[N];
bool used[N];
vector < int > graph[N];
unordered_set < int > busy;
int root;
int curtime;
int last[N],dp[N];

void merge_lists(vector < pi > &result,const vector < pi > &add)
{
    vector < pi > r;
    r.clear();
    int p1 = 0;
    int p2 = 0;

    while((p1 < result.size() || p2 < add.size()) && r.size() < root)
    {
        if(p1 == result.size())
        {
            if(!used[add[p2].second])
                r.push_back(mp(add[p2].first+1,add[p2].second));
            used[add[p2].second] = true;
            p2++;
        }
        else if(p2 == add.size())
        {
            if(!used[result[p1].second])
                r.push_back(result[p1]);
            used[result[p1].second] = true;
            p1++;
        }
        else if(result[p1].first < add[p2].first+1)
        {
            if(!used[add[p2].second])
                r.push_back(mp(add[p2].first+1,add[p2].second));
            used[add[p2].second]=true;
            p2++;
        }
        else
        {
            if(!used[result[p1].second])
                r.push_back(result[p1]);
            used[result[p1].second]=true;
            p1++;
        }
    }

    result = r;

    rep(i,0,result.size())
        used[result[i].second]=false;
    return;
}

void precalc()
{
    rep(i,1,n+1)
        longest[i].push_back(mp(0,i));

    rep(i,1,n+1)
    {
        rep(j,0,graph[i].size())
        {
            int v = graph[i][j];
            merge_lists(longest[v],longest[i]);
        }
    }

    return;
}

int solve_smart(int target)
{
    dp[target]=-1;
    if(busy.count(target)==0)
        dp[target] = 0;

    rep(i,1,target)
    {
        if(last[i] != curtime)
        {
            if(busy.count(i) != 0)
                continue;
            dp[i] = 0;
        }
        last[i] = curtime;

        rep(j,0,graph[i].size())
        {
            int v = graph[i][j];

            if(last[v] != curtime)
                dp[v] = -1;
            dp[v]=max(dp[i]+1,dp[v]);
            last[v]=curtime;
        }
    }

    return dp[target];
}

int solve_simple(int target)
{
    rep(i,0,longest[target].size())
    {
        if(busy.count(longest[target][i].second) == 0)
            return longest[target][i].first;
    }

    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;

    root = 200;

    rep(i,0,m)
    {
        int a,b;
        cin >> a >> b;
        graph[a].push_back(b);
    }

    precalc();

    rep(i,0,q)
    {
        curtime=i+1;
        int t,y,a;
        busy.clear();
        cin >> t >> y;

        rep(j,0,y)
        {
            cin >> a;
            busy.insert(a);
        }

        if(y >= root)
            cout << solve_smart(t) << "\n";
        else
            cout << solve_simple(t) << "\n";
    }

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge_lists(std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while((p1 < result.size() || p2 < add.size()) && r.size() < root)
            ~~~^~~~~~~~~~~~~~~
bitaro.cpp:34:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while((p1 < result.size() || p2 < add.size()) && r.size() < root)
                                  ~~~^~~~~~~~~~~~
bitaro.cpp:34:63: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while((p1 < result.size() || p2 < add.size()) && r.size() < root)
                                                      ~~~~~~~~~^~~~~~
bitaro.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(p1 == result.size())
            ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(p2 == add.size())
                 ~~~^~~~~~~~~~~~~
bitaro.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bitaro.cpp:68:9:
     rep(i,0,result.size())
         ~~~~~~~~~~~~~~~~~           
bitaro.cpp:68:5: note: in expansion of macro 'rep'
     rep(i,0,result.size())
     ^~~
bitaro.cpp: In function 'void precalc()':
bitaro.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bitaro.cpp:80:13:
         rep(j,0,graph[i].size())
             ~~~~~~~~~~~~~~~~~~~     
bitaro.cpp:80:9: note: in expansion of macro 'rep'
         rep(j,0,graph[i].size())
         ^~~
bitaro.cpp: In function 'int solve_smart(int)':
bitaro.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bitaro.cpp:106:13:
         rep(j,0,graph[i].size())
             ~~~~~~~~~~~~~~~~~~~     
bitaro.cpp:106:9: note: in expansion of macro 'rep'
         rep(j,0,graph[i].size())
         ^~~
bitaro.cpp: In function 'int solve_simple(int)':
bitaro.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bitaro.cpp:122:9:
     rep(i,0,longest[target].size())
         ~~~~~~~~~~~~~~~~~~~~~~~~~~  
bitaro.cpp:122:5: note: in expansion of macro 'rep'
     rep(i,0,longest[target].size())
     ^~~

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