ICPC2025西安区域赛题解

//C
#include <bits/stdc++.h>
using namespace std;
int n,m,q,lst[1000010],sm;
int cnt[1000010],ll,rr;
list<int> edg[1000010];
vector<int> orl[1000010];
void Del(int u){if(edg[u].size()>1){for(list<int>::iterator it=edg[u].begin();it!=edg[u].end();++it){if(cnt[*it]==3){sm--;}cnt[*it]--;}}for(list<int>::iterator it=edg[u].begin();it!=edg[u].end();++it){if(edg[*it].size()==2){for(list<int>::iterator itt=edg[*it].begin();itt!=edg[*it].end();++itt){if(cnt[*itt]==3){sm--;}cnt[*itt]--;}continue;}if(edg[*it].size()>2){if(cnt[u]==3){sm--;}cnt[u]--;}}for(list<int>::iterator it=edg[u].begin();it!=edg[u].end();++it){edg[*it].pop_back();}
}
void Add(int u){for(int i=0;i<orl[u].size();i++){int v=orl[u][i];if(ll<=v&&rr>=v){edg[u].push_back(v);edg[v].push_front(u);}}if(edg[u].size()>1){for(list<int>::iterator it=edg[u].begin();it!=edg[u].end();++it){cnt[*it]++;if(cnt[*it]==3){sm++;}}}for(list<int>::iterator it=edg[u].begin();it!=edg[u].end();++it){if(edg[*it].size()==2){for(list<int>::iterator itt=edg[*it].begin();itt!=edg[*it].end();++itt){cnt[*itt]++;if(cnt[*itt]==3){sm++;}}continue;}if(edg[*it].size()>2){cnt[u]++;if(cnt[u]==3){sm++;}}}
}
void solve(){rr=n;for(ll=n;ll>=1;ll--){Add(ll);while(sm){//cout<<rr<<endl;
            Del(rr);rr--;}lst[ll]=rr;//cout<<ll<<" - "<<lst[ll]<<endl;
    }
}
int main(){ios::sync_with_stdio(0);cin>>n>>m>>q;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;orl[a].push_back(b);orl[b].push_back(a);}for(int i=1;i<=n;i++){sort(orl[i].begin(),orl[i].end());}solve();while(q--){int l,r;cin>>l>>r;if(r>lst[l]){cout<<"NO"<<endl;continue;}cout<<"YES"<<endl;}
}

//I
#include <bits/stdc++.h>
using namespace std;
int n,m,a[5050][5050],siz[1000010],lca[5050][5050],fa[1000010];
int main(){ios::sync_with_stdio(0);cin>>n;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){cin>>a[i][j];a[j][i]=a[i][j];}}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int lcaa=a[1][i]^a[1][j]^a[i][j];lca[j][i]=lca[i][j]=lcaa;}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(lca[i][j]==i){siz[i]++;}}}for(int i=2;i<=n;i++){int fl=0;for(int j=1;j<=n;j++){if(i==j||lca[i][j]!=j){continue;}if(siz[j]<siz[fl]||fl==0){fl=j;}}fa[i]=fl;}for(int i=2;i<=n;i++){cout<<i<<" "<<fa[i]<<endl;}
}