QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#869498#8615. Equal Stringsucup-team5008#TL 0ms0kbC++201.3kb2025-01-25 10:30:542025-01-25 10:31:05

Judging History

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

  • [2025-01-25 10:31:05]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2025-01-25 10:30:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep2(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define rep(i,j) rep2(i,0,j)
#define rrep2(i,j,k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i,j) rrep2(i,j,0)
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
#define eb emplace_back
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
const ll inf=LLONG_MAX/4;
template<typename T>
bool chmin(T& a,T b){return a>b?a=b,1:0;}
template<typename T>
bool chmax(T& a,T b){return a<b?a=b,1:0;}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	ll n,m,q;cin>>n>>m>>q;
	vvp query(n);
	vl a(n);
	rep(i,n) a[i]=i;
	rep(i,m){
		ll x,y;cin>>x>>y;
		--x,--y;
		query[a[x]].eb(i,y);
		query[a[y]].eb(i,x);
		swap(a[x],a[y]);
	}
	while(q--){
		ll k;cin>>k;
		vl b(k);
		map<ll,ll> curr;
		rep(i,k) cin>>b[i], --b[i], curr[b[i]]=b[i];
		vector<tuple<ll,ll,ll>> c;
		set<ll> s;
		for(auto el:b){
			s.insert(el);
			for(auto el2:query[el]) c.eb(el2.first,el,el2.second);
		}
		sort(all(c));
		ll ans=-1;
		ll last=-1;
		for(auto [idx,i,j]: c){
			if(last != idx){
				if((*s.rbegin())-(*s.begin()) == k-1){
					ans=last;
					break;
				}
			}
			s.erase(curr[i]);
			curr[i]=j;
			s.insert(j);
			last=idx;
		}
		if(ans==-1) ans=last;
		ans++;
		cout<<ans<<"\n";
	}
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

4

output:


result: