Submission #172188

#	Time	Username	Problem	Language	Result	Execution time	Memory
172188		HellAngel	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	24 ms	17528 KiB

bitaro

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 2e5 + 7;
const int magic = 320;
int n, m, q, dp[maxn], block[maxn];
vector<int> qr;

vector<int> vt[maxn], vt2[maxn];
vector<pair<int, int>> graph[maxn];

void Merge(int x, int y)
{
    int cntx = 0;
    int cnty = 0;
    vector<pair<int, int>> newvt = {};
    while(cntx < graph[x].size() || cnty < graph[y].size())
    {
        if(newvt.size() == magic) break;
        if(cntx == graph[x].size()) newvt.push_back({graph[y][cnty].first + 1, graph[y][cnty].second}), cnty++;
        else if(cnty == graph[y].size()) newvt.push_back(graph[x][cntx++]);
        else
        {
            if(graph[y][cnty].first + 1 > graph[x][cntx].first)
            {
                newvt.push_back({graph[y][cnty].first + 1, graph[y][cnty].second});
                cnty++;
            }
            else newvt.push_back(graph[x][cntx++]);
        }
    }
    graph[x] = newvt;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        vt[v].push_back(u);
        vt2[u].push_back(v);
    }
    for(int i = 1; i <= n; i++)
    {
        graph[i].push_back({0, i});
        for(auto j: vt[i])
        {
            Merge(i, j);
        }
    }
    for(int i = 1; i <= q; i++)
    {
        int u, c;
        cin >> u >> c;
        for(int j = 1; j <= c; j++)
        {
            int x;
            cin >> x;
            block[x] = true;
            qr.push_back(x);
        }
        if(c < magic)
        {
            bool ok = false;
            for(int j = 0; j < graph[u].size(); j++)
            {
                if(!block[graph[u][j].second])
                {
                    cout << graph[u][j].first << '\n';
                    ok = true;
                    break;
                }
            }
            if(!ok) cout << -1 << '\n';
        }
        else
        {
            int ans = 0;
            dp[u] = 0;
            for(int j = u - 1; j >= 1; j--)
            {
                if(block[j]) continue;
                dp[j] = -1e15;
                for(auto x: vt2[j])
                {
                    if(x <= u)
                    {
                        dp[j] = max(dp[j], dp[x] + 1);
                    }
                }
                ans = max(ans, dp[j]);
            }
            if(ans > 0)
            {
                cout << ans << '\n';
            }
            else
            {
                if(block[u]) cout << -1 << '\n';
                else cout << u << '\n';
            }
        }
        for(auto i: qr) block[i] = 0;
        qr = {};
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'void Merge(long long int, long long int)':
bitaro.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cntx < graph[x].size() || cnty < graph[y].size())
           ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:19:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cntx < graph[x].size() || cnty < graph[y].size())
                                     ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cntx == graph[x].size()) newvt.push_back({graph[y][cnty].first + 1, graph[y][cnty].second}), cnty++;
            ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(cnty == graph[y].size()) newvt.push_back(graph[x][cntx++]);
                 ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:72:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < graph[u].size(); j++)
                            ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:41:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:41:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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