Submission #546506

#	Time	Username	Problem	Language	Result	Execution time	Memory
546506		stefantaga	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1506 ms	250260 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
vector <int> v[100005],inv[100005];
int n,m,q,i,fr[100005],val[100005],ok[100005],distfin[100005],teste;
pair <int,int >  dist[100005][305];
int mar[100005];
vector <pair <int,int>> acum;
vector <int> salut;
bool compare (pair <int,int> a,pair <int,int> b)
{
    return a.second>b.second;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m>>teste;
    for (i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        if (x>y)
        {
            swap(x,y);
        }
        inv[y].push_back(x);
    }
    int bucket =150;

    for (i=1;i<=n;i++)
    {
        int numar=0;
        acum.clear();
        salut.clear();
        acum.push_back({i,0});
        for (int j=0;j<inv[i].size();j++)
        {
            int nod = inv[i][j];
            for (int k=1;k<=mar[nod];k++)
            {
                acum.push_back({dist[nod][k].first,dist[nod][k].second+1});
            }
        }
        int lim = min((int)acum.size(),bucket);
        sort (acum.begin(),acum.end(),compare);
        for (int j=0;j<lim;j++)
        {
            if (fr[acum[j].second]==0)
            {
                fr[acum[j].second]=1;
                mar[i]++;
                dist[i][mar[i]]=acum[j];
                salut.push_back(acum[j].second);
            }
        }
        for (int j=0;j<salut.size();j++)
        {
            fr[salut[j]]=0;
        }
    }
    for (i=1;i<=n;i++)
    {
        fr[i]=0;
    }
    for (;teste--;)
    {
        int nod,nr;
        cin>>nod >> nr;
        for (i=1;i<=nr;i++)
        {
            cin>>val[i];
            fr[val[i]]=1;
        }

        if (nr>=bucket)
        {
            vector<int> dp(n, -1);
			for (int i = 0; i <= nod; i ++){
				if (fr[i]==0){
					dp[i] = max(dp[i], 0);
				}
				for (int j = 0; j < (int)inv[i].size(); j ++){
					if (dp[inv[i][j]] != -1) dp[i] = max(dp[i], dp[inv[i][j]] + 1);
				}
			}
			cout << dp[nod] << '\n';
        }
        else
        {
            int solfin=-1;
            for (int j=1;j<=mar[nod];j++)
            {
                int nod2 = dist[nod][j].first;
                if (fr[nod2]==0)
                {
                    solfin=max(solfin,dist[nod][j].second);
                }
            }
            cout<<solfin<<'\n';
        }
        for (i=1;i<=nr;i++)
        {
            fr[val[i]]=0;
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j=0;j<inv[i].size();j++)
      |                      ~^~~~~~~~~~~~~~
bitaro.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int j=0;j<salut.size();j++)
      |                      ~^~~~~~~~~~~~~
bitaro.cpp:37:13: warning: unused variable 'numar' [-Wunused-variable]
   37 |         int numar=0;
      |             ^~~~~

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