QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#606097#8757. 图UESTC_Snow_HalationRE 59ms20488kbC++142.5kb2024-10-02 22:07:232024-10-02 22:07:23

Judging History

你现在查看的是最新测评结果

  • [2024-10-02 22:07:23]
  • 评测
  • 测评结果:RE
  • 用时:59ms
  • 内存:20488kb
  • [2024-10-02 22:07:23]
  • 提交

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 ...

output:


result: