제출 #172203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172203		HellAngel	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1609 ms	277432 KiB

bitaro

/// bai tri tue vai loz cac ban a
#include <bits/stdc++.h>

using namespace std;

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

vector<int> vt[maxn], vt2[maxn];
vector<pair<int, int>> graph[maxn];
vector<pair<int, int>> newvt = {};

void Add(const pair<int, int> &p)
{
    if(!inside[p.second])
    {
        newvt.push_back(p);
        inside[p.second] = true;
    }
}

void Merge(int x, int y)
{
    int cntx = 0;
    int cnty = 0;
    newvt = {};
    while(cntx < graph[x].size() || cnty < graph[y].size())
    {
        if(newvt.size() == magic) break;
        if(cntx == graph[x].size())
        {
            Add({graph[y][cnty].first + 1, graph[y][cnty].second}), cnty++;
        }
        else if(cnty == graph[y].size()) Add(graph[x][cntx++]);
        else
        {
            if(graph[y][cnty].first + 1 > graph[x][cntx].first)
            {
                Add({graph[y][cnty].first + 1, graph[y][cnty].second});
                cnty++;
            }
            else Add(graph[x][cntx++]);
        }
    }
    graph[x] = newvt;
    for(auto i: graph[x])
    {
        inside[i.second] = 0;
    }
}

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--)
            {
                dp[j] = -1e9;
                for(auto x: vt2[j])
                {
                    if(x <= u)
                    {
                        dp[j] = max(dp[j], dp[x] + 1);
                    }
                }
                if(!block[j])
                ans = max(ans, dp[j]);
            }
            if(ans > 0)
            {
                cout << ans << '\n';
            }
            else
            {
                if(block[u]) cout << -1 << '\n';
                else cout << 0 << '\n';
            }
        }
        for(auto i: qr) block[i] = 0;
        qr = {};
    }
}

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

bitaro.cpp: In function 'void Merge(int, int)':
bitaro.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cntx < graph[x].size() || cnty < graph[y].size())
           ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:30:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cntx < graph[x].size() || cnty < graph[y].size())
                                     ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cntx == graph[x].size())
            ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(cnty == graph[y].size()) Add(graph[x][cntx++]);
                 ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:90:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < graph[u].size(); j++)
                            ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:59: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:59:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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