QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#869498 | #8615. Equal Strings | ucup-team5008# | TL | 0ms | 0kb | C++20 | 1.3kb | 2025-01-25 10:30:54 | 2025-01-25 10:31:05 |
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