oj.uz

답안 #95067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95067 2019-01-27T07:39:11 Z omidazadi Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 14 ms 8952 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=1e2+10;

vector <pll> e[MAXN];
vector <ll> in[MAXN];
vector <ll> out[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++)
			{
				e[i].pb(mp(e[v][u].X+1 , e[v][u].Y));
			}
		}

		sort(e[i].begin() , e[i].end() , std::greater<pll>());

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

	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;
			dp[t]=0;

			for(ll j=t;j>=1;j--)
			{
				dp[j]=(j==t ? 0 : -1);

				for(ll u=0;u<out[j].size() && out[j][u]<=t;u++)
				{
					if (dp[out[j][u]]!=-1)
					{
						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:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<in[i].size();j++)
              ~^~~~~~~~~~~~~
bitaro.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(ll u=0;u<e[v].size();u++)
               ~^~~~~~~~~~~~
bitaro.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll u=0;u<out[j].size() && out[j][u]<=t;u++)
                ~^~~~~~~~~~~~~~
bitaro.cpp:117: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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 6 ms 7416 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 7 ms 7416 KB Output is correct
5 Incorrect 14 ms 8952 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 6 ms 7416 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 7 ms 7416 KB Output is correct
5 Incorrect 14 ms 8952 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 6 ms 7416 KB Output is correct
3 Correct 6 ms 7424 KB Output is correct
4 Correct 7 ms 7416 KB Output is correct
5 Incorrect 14 ms 8952 KB Output isn't correct
6 Halted 0 ms 0 KB -