QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#322403#121. Bitaro's PartyNintsiChkhaidze0 2ms5616kbC++202.3kb2024-02-06 23:40:462024-02-06 23:40:47

Judging History

你现在查看的是最新测评结果

  • [2024-02-06 23:40:47]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:5616kb
  • [2024-02-06 23:40:46]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,
using namespace std;

const int N = 2e5 + 3;

int b[N],id,vis[N],fix[N],dp[N],f[N];
vector <int> g[N],v[N],ord;
vector <pii> paths[N];

void topsort(int x){
	vis[x]=1;
	for (int to: v[x])
		if (!vis[to]) topsort(to);
	ord.pb(x);
}

vector <pii> merge(vector <pii> x,vector <pii> y){
	for (int i = 0; i < x.size(); i++)
		x[i].f += 1;
		
	++id;
	int l1 = 0,l2 = 0;
	vector <pii> vec;
	while (l1 < x.size() || l2 < y.size()){
		while (l1 < x.size() && fix[x[l1].s] == id) l1++;
		while (l2 < y.size() && fix[y[l2].s] == id) l2++;
		
		if (l1 == x.size()) {
			vec.pb(y[l2]);
			fix[y[l2].s] = id;
			++l2;
			continue;
		}
		
		if (l2 == y.size()){
			vec.pb(x[l1]);
			fix[x[l1].s] = id;
			++l1;
			continue;
		}
		
		if (x[l1] > y[l2]) {
			vec.pb(x[l1]);
			fix[x[l1].s] = id;
			++l1;
			continue;
		}
		
		vec.pb(y[l2]);
		fix[y[l2].s] = id;
		++l2;
	}
	
	return vec;
}
signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

    int n,m,q;
    cin>>n>>m>>q;
   
    for (int i = 1; i <= m; i++){
		int a,b;
		cin>>a>>b;
		g[b].pb(a);
		v[a].pb(b);
    }
    
    for (int i = 1; i <= n; i++){
    	if (!vis[i]) topsort(i);
 	}
 	reverse(ord.begin(),ord.end());
 	
 	int Bl = 320;
 	for (int x: ord){
		vector <pii> cur;
		cur.pb({0,x});
		for (int prev: g[x]){
			cur = merge(paths[prev], cur);
		}	
		
		for (int i = 0; i < cur.size(); i++){
			if (paths[x].size() == Bl) break;
			paths[x].pb(cur[i]); 
		}
	}
	
    while (q--){
    	int T,k;
    	cin>>T>>k;
    	for (int i = 1; i <= k; i++){
    		int x;
    		cin>>x;
    		b[i] = x;
    		f[x] = 1;
		}
			
		int ans=0;
		if (k < Bl){
			for (auto [l,r]: paths[T]){
				if (!f[r]) {ans = l; break;}
			}
			cout<<ans<<endl;
		}else{
			for (int i = 1; i <= n; i++){
				if (f[i]) dp[i] = -1e9;
				else dp[i] = 0;
			}
			
			for (int x: ord){
				for (int prev: g[x]){
					dp[x] = max(dp[x],dp[prev] + 1);
				}
			}
			if (dp[T] < 0) cout<<-1<<endl;
			else cout<<dp[T]<<endl;
		}
		for (int i = 1; i <= k; i++)
			f[b[i]] = 0;
	}
	
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 7
Accepted
time: 1ms
memory: 3504kb

input:

1 0 1
1 0

output:

0

result:

ok single line: '0'

Test #2:

score: -7
Wrong Answer
time: 2ms
memory: 5616kb

input:

1 0 1
1 1 1

output:

0

result:

wrong answer 1st lines differ - expected: '-1', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%