QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#606097 | #8757. 图 | UESTC_Snow_Halation | RE | 59ms | 20488kb | C++14 | 2.5kb | 2024-10-02 22:07:23 | 2024-10-02 22:07:23 |
Judging History
answer
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define FOR() ll le=e[u].size();for(ll i=0;i<le;i++)
#define QWQ cout<<"QwQ\n";
#define ll long long
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
const ll N=501010;
const ll qwq=303030;
const ll inf=0x3f3f3f3f;
inline ll read() {
ll sum = 0, ff = 1; char c = getchar();
while(c<'0' || c>'9') { if(c=='-') ff = -1; c = getchar(); }
while(c>='0'&&c<='9') { sum = sum * 10 + c - '0'; c = getchar(); }
return sum * ff;
}
ll T;
ll n,m,K;
vector <ll> e[N];
unordered_map <ll,ll> f;
ll tot;
ll fa[N],zhi[N];
ll st[N],cnt;
ll find(ll x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
ll _id(ll h,ll x) {
return (h-1) * n + x;
}
inline bool check(ll h,ll x,ll y) {
ll u = _id(h,x), v = _id(h,y);
if(f.find(u)==f.end() || f.find(v)==f.end()) return 0;
ll xx = find(f[u]), yy = find(f[v]);
if(xx==yy) return 1;
return 0;
}
bool link = 0;
void DFS(ll u,ll ff,ll goal) {
st[++cnt] = u;
if(goal==u) { link = 1; return ; }
for(ll v : e[u]) {
if(v==ff) continue;
DFS(v,u,goal);
if(link) return ;
}
if(!link) cnt--;
}
void chushihua() {
f.clear();
for(ll i=1;i<=tot;i++) e[i].clear();
tot = 0;
}
int main() {
ll x,y;
T = read();
while(T--) {
chushihua();
n = read(); m = read();
for(int i=1;i<=2*m;i++) fa[i] = i;
K = m/(n-1);
if(m%(n-1)) K++;
ll ans1 = 0, ans2 = 0;
while(m--) {
x = read(); y = read();
if(ans1) continue;
ll l = 1, r = K-1, mid, res = 0;
while(l<=r) {
mid = l+r >> 1;
if(check(mid,x,y)) l = mid+1, res = mid;
else r = mid-1;
}
ll u = _id(res+1,x), v = _id(res+1,y);
if(f.find(u)==f.end()) f[u] = ++tot, zhi[tot] = x;
if(f.find(v)==f.end()) f[v] = ++tot, zhi[tot] = y;
fa[ f[u] ] = f[v];
e[ f[u] ].push_back( f[v] );
e[ f[v] ].push_back( f[u] );
if(res+1==K) ans1 = x, ans2 = y;
}
cout<<ans2<<" "<<ans1<<"\n";
for(ll i=1;i<=K;i++) {
ll u = f[_id(i,ans1)], v = f[_id(i,ans2)];
link = 0;
DFS(u,u,v);
cout<<cnt<<" ";
while(cnt) cout<<zhi[st[cnt--]]<<" ";
cout<<"\n";
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 59ms
memory: 20488kb
input:
10000 2 20 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 20 2 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 2 20 1 2 2 1 1 2 1 2 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 20 1 2 2 1 2 1 1 2 1 2 1 2 2 1 1 2 2 ...
output:
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 1 2 2...
result:
ok Answer correct. (10000 test cases)
Test #2:
score: -100
Runtime Error
input:
10000 5 20 2 1 2 5 5 3 3 1 4 5 1 4 4 3 4 5 3 5 5 4 2 3 5 2 3 4 3 5 1 4 4 3 4 2 2 1 1 3 5 1 5 20 4 2 1 3 1 2 4 5 2 4 3 1 5 3 5 1 4 5 4 3 2 4 1 4 4 3 5 2 1 2 3 5 1 5 4 1 3 4 4 3 5 20 1 4 1 3 1 5 5 1 4 5 3 4 4 5 2 3 1 2 2 4 4 5 4 5 2 4 2 5 4 2 4 3 4 2 2 5 2 1 3 1 5 20 2 5 2 3 4 5 4 2 3 4 2 1 5 4 2 5 2 ...