oj.uz

Submission #95093

# Submission time Handle Problem Language Result Execution time Memory
95093 2019-01-27T08:46:08 Z omidazadi Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 9 ms 7772 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pll pair <ll , ll>

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair

#define X first
#define Y second

#define LB(x) ((x) & -(x))
#define BIT(x , y) (((x) >> (y)) & 1)

#define ll int

const ll MAXN=1e5+10;
const ll SQ=0;

vector <pll> e[MAXN];
vector <ll> in[MAXN];
vector <ll> out[MAXN];

vector <pll> f;

ll w[MAXN];
ll z[MAXN];
ll dp[MAXN];

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

	ll n , m , q;
	cin>>n>>m>>q;

	for(ll i=1;i<=m;i++)
	{
		ll v , u;
		cin>>v>>u;

		out[v].pb(u);
		in[u].pb(v);
	}

	for(ll i=1;i<=n;i++)
	{
		for(ll j=0;j<in[i].size();j++)
		{
			ll v=in[i][j];

			for(ll u=0;u<e[v].size();u++)
			{
				f.pb(mp(e[v][u].X+1 , e[v][u].Y));
			}
		}

		sort(f.begin() , f.end() , std::greater<pll>());

		for(ll j=0;j<f.size();j++)
		{
			if (e[i].size()==SQ)
			{
				break;
			}

			if (w[f[j].Y]!=i)
			{
				w[f[j].Y]=i;
				e[i].pb(f[j]);
			}
		}

		if (e[i].size()<SQ)
		{
			e[i].pb(mp(0 , i));
		}

		f.clear();
	}

	for(ll i=1;i<=q;i++)
	{
		ll t , y;
		cin>>t>>y;

		for(ll j=1;j<=y;j++)
		{
			ll x;
			cin>>x;

			z[x]=i;
		}

		if (y>=SQ)
		{
			ll res=-1;
			memset(dp, -63, sizeof(dp));
			dp[t] = 0;
			for(ll j=t - 1;j>=1;j--)
			{

				for(ll u=0;u<out[j].size();u++)
				{
					if (out[j][u]<=t)
					{
						dp[j]=max(dp[j] , dp[out[j][u]]+1);
					}
				}

				if (z[j]!=i)
				{
					res=max(res , dp[j]);
				}
			}

			cout<<res<<endl;
		}
		else
		{
			bool flag=false;

			for(ll j=0;j<e[t].size();j++)
			{
				if (z[e[t][j].Y]!=i)
				{
					cout<<e[t][j].X<<endl;
					flag=true;
					break;
				}
			}

			if (!flag)
			{
				cout<<-1<<endl;
			}
		}
	}
}

Compilation message

bitaro.cpp:21:0: warning: "ll" redefined
 #define ll int
 
bitaro.cpp:5:0: note: this is the location of the previous definition
 #define ll long long
 
bitaro.cpp: In function 'int main()':
bitaro.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<in[i].size();j++)
              ~^~~~~~~~~~~~~
bitaro.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(ll u=0;u<e[v].size();u++)
               ~^~~~~~~~~~~~
bitaro.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<f.size();j++)
              ~^~~~~~~~~
bitaro.cpp:110:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll u=0;u<out[j].size();u++)
                ~^~~~~~~~~~~~~~
bitaro.cpp:130:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(ll j=0;j<e[t].size();j++)
               ~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -