Submission #790506

#	Time	Username	Problem	Language	Result	Execution time	Memory
790506		KiaRez	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1909 ms	124512 KiB

bitaro

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 2e5+25, SQ=110, lg=18;
ll Mod = 1e9+7;
//ll Mod = 998244353;

ll MOD(ll a, ll mod=Mod)                   {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    a=MOD(a);
    while (b) {
        if (b & 1) ans = MOD(ans*a);
        b >>= 1;
        a = MOD(a*a);
    }
    return ans;
}

int n, m, qu, deg[N], mark[N], mark2[N], dist[N];
vector<pii> vec[N];
vector<int> adj[N], rev[N];

void init() {
	queue<int> q;
	for(int i=1; i<=n; i++) {
		deg[i] = size(rev[i]);
		if(deg[i] == 0) q.push(i);
	}

	while(size(q)) {
		int v = q.front();
		q.pop();
		priority_queue<pii, vector<pii>, greater<pii>> pq;
		for(auto u : rev[v]) {
			for(int i=size(vec[u])-1; i>=0; i--) {
				//if(size(pq)==SQ && pq.top().F>=vec[u][i].F+1) break;
				pq.push({vec[u][i].F+1, vec[u][i].S});
				if(size(pq) > SQ) pq.pop();
			}
		}
		if(size(pq) < SQ) pq.push({0, v});
		while(size(pq)) {
			vec[v].pb(pq.top());
			pq.pop();
		}
		for(auto u : adj[v]) {
			deg[u]--;
			if(deg[u] == 0) q.push(u);
		}
	}
}

void KIAREZ(int v) {
	fill(dist, dist+n+2, 0);
	fill(deg, deg+n+2, 0);
	queue<int> q;
	
	for(int i=1; i<=n; i++) {
		deg[i] = size(rev[i]);
		if(deg[i] == 0) q.push(i);
	}

	while(size(q)) {
		int u = q.front();
		q.pop();
		for(auto w : adj[u]) {
			if(mark[u]==0 || dist[u]>0) dist[w] = max(dist[u] + 1, dist[w]);
			deg[w] --;
			if(deg[w] == 0)q.push(w);
		}
	}

	if(dist[v]==0 && mark[v]==1) cout<<-1<<endl;
	else cout<<dist[v]<<endl;
}

void kiarez(int v) {
	int ans = -1;
	for(int i=size(vec[v])-1; i>=0; i--) {
		if(mark[vec[v][i].S] == 0) {ans = vec[v][i].F; break;}
	}
	cout<<ans<<endl;
}

int main () {
	ios;

	cin>>n>>m>>qu;
	for(int v,u,i=1; i<=m; i++) {
		cin>>v>>u;
		adj[v].pb(u);
		rev[u].pb(v);
	}

	init();

	while(qu--) {
		int t,y;
		cin>>t>>y;
		vector<int> c;
		
		for(int v,i=1; i<=y; i++) {
			cin>>v;
			c.pb(v);
			mark[v] = 1;
		}

		if(y >= SQ) {
			KIAREZ(t);
		} else {
			kiarez(t);
		}

		for(auto it : c) mark[it] = 0;
	}

	return 0;
}

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