QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#679768 | #3846. Link-Cut Tree | lhw | WA | 181ms | 15036kb | C++14 | 2.0kb | 2024-10-26 18:28:39 | 2024-10-26 18:28:39 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<array>
#include<random>
#include<string>
#include<time.h>
#include<cstring>
#include<set>
#include<cmath>
#include<queue>
#define int long long
#define endl '\n'
#define F first
#define S second
#define sz size()
#define ln cout<<'\n'
#define B begin()
#define pb push_back
#define D end()
#define pii pair<int,int>
using namespace std;
const int N=1e5+10;
const int mod=1e9;
int n,m;
int f[N];
struct Nod{
int u;
int v;
int w;
}g[N];
bool cmp(Nod a,Nod b)
{
return a.w<b.w;
}
int find1(int u)
{
if(u!=f[u])f[u]=find1(f[u]);
return f[u];
}
struct NN{
int u;
int v;
int c;
};
vector<NN> ss;
bool vis[N];
vector<int> ans;
bool ok=0;
void dfs(int u,int pa,vector<vector<pair<int,int>>>&mp)
{
if(ok)return;
vis[u]=1;
for(auto t:mp[u])
{
int v=t.first;
if(v==pa)continue;
ss.push_back({u,v,t.second});
if(vis[v]==1)
{
while(ss[ss.size()-1].u!=v)
{
ans.push_back(ss[ss.size()-1].c);
ss.pop_back();
}
ans.push_back(ss[ss.size()-1].c);
ok=1;
return;
}
dfs(v,u,mp);
if(ok)return;
}
ss.pop_back();
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
vis[i]=0;
}
ans.clear();ss.clear();
ok=0;
vector<vector<pair<int,int>>> mp(n+1);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=0;i<m;i++)
{
int u,v;
cin>>u>>v;
g[i]={u,v,i};
}
sort(g,g+m,cmp);
for(int i=0;i<m;i++)
{
int u=g[i].u;
int v=g[i].v;
int fa=find1(u);
int fb=find1(v);
mp[u].push_back({v,i});
mp[v].push_back({u,i});
if(fa==fb)
{
dfs(g[0].u,-1,mp);
sort(ans.begin(),ans.end());
cout<<ans[0]+1;
for(int i=1;i<ans.size();i++)
{
cout<<' '<<ans[i]+1;
}
cout<<endl;
return;
}
if(fa!=fb)f[find1(u)]=f[find1(v)];
}
cout<<-1<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int tc=1;
cin>>tc;
while(tc--)
{
solve();
}
//cout<<"dafc";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5620kb
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:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 181ms
memory: 15036kb
input:
1658 9 20 6 4 5 8 1 7 2 3 3 8 3 1 4 8 5 3 7 6 1 6 4 9 4 1 9 3 2 5 4 5 8 9 1 8 4 2 5 7 3 6 14 78 13 12 10 8 2 10 6 13 2 14 13 1 14 10 9 6 2 13 8 3 9 8 5 6 14 12 8 1 9 14 9 5 12 6 5 10 3 12 10 4 8 5 9 10 6 8 1 6 12 4 3 13 1 5 10 3 13 9 10 13 2 5 4 7 7 1 7 6 9 3 2 12 1 10 9 1 1 14 3 1 3 4 11 1 11 6 7 1...
output:
2 5 8 2 1 3 4 2 3 4 2 1 3 4 5 9 3 4 7 12 1 2 3 8 10 11 2 3 5 7 12 13 14 15 16 1 2 3 5 1 2 4 1 3 4 1 2 3 1 2 3 10 11 15 1 5 6 1 5 7 1 2 3 4 -1 1 3 6 -1 1 2 3 5 -1 -1 6 8 9 10 11 16 1 2 6 2 3 4 -1 -1 7 8 12 13 18 -1 1 4 8 12 1 1 1 2 3 4 3 5 6 3 4 6 8 -1 1 2 3 5 6 1 3 4 1 3 5 8 1 2 4 6 7 8 11 12 13 1 4...
result:
wrong answer 2nd lines differ - expected: '3 5 7', found: '2'