Submission #160444

#	Time	Username	Problem	Language	Result	Execution time	Memory
160444		combi1k1	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1901 ms	416936 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define pb  push_back
#define ii  pair<int,int>

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 1e5 + 1;
const int   B   = 317;

vector<int> g[N];
vector<ii>  opt[N];

int vis[N];
int ban[N];
int len[N];
int tot = 1;

void pus(int u,int v)  {
    int a = 0;
    int b = 0;

    for(ii &e : opt[v]) e.X++;

    vector<ii>  clone;

    auto add = [&](ii  e)   {
        if (vis[e.Y] != tot)
            vis[e.Y]  = tot,
            clone.pb(e);
    };

    while (a < opt[u].size() && b < opt[v].size())  {
        if (opt[u][a] < opt[v][b])  {   add(opt[v][b++]);   continue;   }
        if (opt[u][a] > opt[v][b])  {   add(opt[u][a++]);   continue;   }

        clone.pb(opt[u][a]);
        a++;
        b++;
    }
    while (a < opt[u].size())   add(opt[u][a++]);
    while (b < opt[v].size())   add(opt[v][b++]);

    while (clone.size() > B)    clone.pop_back();

    for(ii &e : opt[v]) e.X--;

    opt[u].swap(clone);
}

int dfs(int u)  {
    if (vis[u]) return  0;

    vis[u] = 1;
    opt[u].pb(ii(0,u));

    for(int v : g[u])  {
        dfs(v); tot++;
        pus(u,v);
    }
}
int cal(int u)  {
    if (vis[u]) return  len[u];

    len[u] = (ban[u] ? -N : 0);
    vis[u] = 1;

    for(int v : g[u])
        len[u] = max(len[u],cal(v) + 1);

    return  len[u];
}

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

    int n;  cin >> n;
    int m;  cin >> m;
    int q;  cin >> q;

    FOR(i,0,m)  {
        int x;  cin >> x;
        int y;  cin >> y;
        g[y].pb(x);
    }
    FOR(i,1,n + 1)  if(!vis[i]) dfs(i);
    FOR(i,1,q + 1)  {
        int u;  cin >> u;
        int k;  cin >> k;

        vector<int> vv;

        FOR(i,0,k)  {
            int x;  cin >> x;
            ban[x] = 1;
            vv.pb(x);
        }

        int ans = -1;

        if (k < B)  {
            for(ii  e : opt[u])
            if(!ban[e.Y])
                ans = max(ans,e.X);
        }
        else    {
            fill(vis + 1,vis + 1 + n,0);
            ans = max(ans,cal(u));
        }
        for(int x : vv)
            ban[x] = 0;

        cout << ans << "\n";
    }
}
/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
*/

Compilation message (stderr)

bitaro.cpp: In function 'void pus(int, int)':
bitaro.cpp:37:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size() && b < opt[v].size())  {
            ~~^~~~~~~~~~~~~~~
bitaro.cpp:37:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size() && b < opt[v].size())  {
                                 ~~^~~~~~~~~~~~~~~
bitaro.cpp:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a < opt[u].size())   add(opt[u][a++]);
            ~~^~~~~~~~~~~~~~~
bitaro.cpp:46:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (b < opt[v].size())   add(opt[v][b++]);
            ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'int dfs(int)':
bitaro.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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