QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#692244 | #3846. Link-Cut Tree | telgs# | WA | 3ms | 32332kb | C++17 | 1.4kb | 2024-10-31 14:10:27 | 2024-10-31 14:10:30 |
Judging History
answer
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
using ll=long long;
using pii=pair<ll,ll>;
using ld=long double;
constexpr ll N=1e6+10,mod=1e8-3,INF=1e18;
constexpr ld inf=1e18,eps=1e-5;
ll n,m;
ll p[N],d[N];
bool st[N];
vector<ll> g[N];
map<pii,int> mp;
struct Node{
ll u,v;
}tr[N];
ll find(ll x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void topsort(){
queue<ll> q;
for(int i=1;i<=n;i++){
if(d[i]==1){
q.push(i);
}
}
while(!q.empty()){
ll u=q.front();
q.pop();
for(auto v:g[u]){
--d[v];
// cout<<mp[{min(u,v),max(u,v)}]<<'\n';
st[mp[{min(u,v),max(u,v)}]]=0;
if(d[v]==1){
q.push(v);
}
}
}
}
void solve(){
cin>>n>>m;
mp.clear();
for(int i=1;i<=n;i++){
p[i]=i,d[i]=0;
g[i].clear();
}
for(int i=1;i<=m;i++) st[i]=0;
for(int i=1;i<=m;i++){
cin>>tr[i].u>>tr[i].v;
mp[{min(tr[i].u,tr[i].v),max(tr[i].u,tr[i].v)}]=i;
}
for(int i=1;i<=m;i++){
ll u=tr[i].u,v=tr[i].v;
d[u]++,d[v]++;
g[u].push_back(v),g[v].push_back(u);
st[i]=1;
if(find(u)==find(v)){
topsort();
for(int j=1;j<=m;j++){
if(st[j]) cout<<j<<' ';
}
cout<<'\n';
return;
}else{
p[find(u)]=find(v);
}
}
cout<<"-1\n";
}
int main(){
IOS;
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 32332kb
input:
2 6 8 1 2 2 3 5 6 3 4 2 5 5 4 5 1 4 2 4 2 1 2 4 3
output:
2 4 5 6 -1
result:
wrong answer 1st lines differ - expected: '2 4 5 6', found: '2 4 5 6 '