QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491504 | #8757. 图 | Fffoooo | WA | 1000ms | 10116kb | C++14 | 2.5kb | 2024-07-25 20:00:10 | 2024-07-25 20:00:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int mian(); int main() { return mian(); }
const int N = 1e5 + 15, M = 2e5 + 25;
int n, m, k;
int id(const int i, const int j) { return i + (j - 1) * n; }
struct UF {
int fa[M], siz[M];
void init_fa() { for(int i = 1; i < M; ++i) fa[i] = i, siz[i] = 1; }
int get(const int x) { if( x == fa[x] ) return x; return fa[x] = get(fa[x]); }
void us(int u, int v) {
u = get(u); v = get(v);
if( siz[u] < siz[v] ) swap(u, v);
siz[u] += siz[v]; fa[v] = u;
}
}uf;
vector<int> eg[M];
void add(const int u, const int v) { eg[u].push_back(v); eg[v].push_back(u); }
int fa[N], dep[N];
void dfs_tree(const int u, const int dad) {
fa[u] = dad; dep[u] = dep[dad] + 1;
for(auto v : eg[u]) if( v != dad ) dfs_tree(v, u);
}
void solvp(const int u, const int v) {
//printf("%d %d\n", u, v);
for(int now = 1; now <= k; ++now) {
dfs_tree( id(v, now), 0 );
//printf("%d ", dep[ id(u, now) ]);
int x = id(u, now);
//while( x != 0 ) printf("%d ", ( x - 1 ) % n + 1), x = fa[x];
//puts("");
}
}
void solve() {
scanf("%d%d", &n, &m);
k = ceil( (double)m / (double)(n - 1) );
uf.init_fa();
for(int i = 1; i <= id(n, k); ++i) eg[i].clear();
for(int i = 1, u, v; i <= m; ++i) {
scanf("%d%d", &u, &v);
int l = 1, r = k, now = k + 1;
while( l <= r ) {
const int mid = (l + r) >> 1;//只能二分
if( uf.get( id(u, mid) ) != uf.get( id(v, mid) ) ) r = mid - 1, now = mid;
else l = mid + 1;
}
if( now <= k ) add( id(u, now), id(v, now) ), uf.us( id(u, now), id(v, now) );
}
for(int u = 1; u <= n; ++u) if( uf.get( id(u, k) ) != id(u, k) ) return (void) solvp( u, uf.get( id(u, k) ) % n );
puts("-1");
}
int mian() {
int T; scanf("%d", &T);
while( T-- ) solve();
cout<<clock();
return 0;
} /*
给定一张 $n$ 点 $m$ 条边的图,求一个点对 $(u,v)$ 满足他们之间有 $k=\lceil \dfrac{m}{n-1} \rceil$ 条边不相交的路径
$n\le 10^5, m\le 2\times 10^5$
$1s, 512MB$
考虑直接构造出 $k$ 条路经
那么不妨直接构造出来 $k$ 层图,使得这 $k$ 层图中,任意两个点的路径在 $k$ 张图上互不相交
也就是每一条边只属于一张图。
那么对于每一层图,如果要加入的边 $(u,v)$ 已经联通,那么就加入到下一层图中,一直知道第一个不连通的图中
那么,一层至多有 $n-1$ 条边(一棵树,全联通),于是至少有 $\lceil \dfrac{m}{n-1} \rceil=k$ 层图
找到第 $k$ 层的任意一队点并在下面的层中找到对应的路径即可
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1000ms
memory: 10116kb
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:
998388
result:
wrong answer Integer 998388 violates the range [1, 2] (test case 1)