Atcoder abc301

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
G(计算几何)Ex(图论,lowlink,dsu)

https://atcoder.jp/contests/abc301/tasks

G Worst Picture

三维空间 n个人, 整点坐标(xi > 0,yi,zi), 两两坐标不同

需要选点p(x<0,y,z) , 在 x正向拍照

p,A,B共线，则后面的人不被拍到

想办法找点p 让被拍到的人的人尽量小， 求最小被拍到的人

n 50

x [1,1000]

y,z [-1000,1000]

4s

1024mb

我的思路

二维空间几何都还不熟，这里来个3维的

但为什么看起来 逻辑很简单，只是实现不知道

既然N 只有50, 那么就是 暴力选4个点， 这样两条线找交点

这样再去枚举交点

一个特殊情况是有一条线上 有很多点，那么这条线上任意一个位置都可以

那么问题来了，如何找三维空间中的交点

感觉就是先抛弃 第3维，直接计算(x,y)的交点, 再验证z?

似乎卡着时间过了, 一次TLE一个点，一次AC

代码

https://atcoder.jp/contests/abc301/submissions/42097253

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
ll gcd(ll a,ll b) {
  if(b<0) b=-b;
  return (b == 0)?a:gcd(b,a%b);
}
using frac=pair<ll,ll>; // {a,b} = a/b
using point=array<frac,3>;
using direct=array<frac,3>;
using line=pair<point,direct>;
const frac ZERO{0,1};

frac norm(const frac&a){
  auto [t,b]=a;
  if(t==0) return {0,1};
  if(t < 0) {
    t=-t;
    b=-b;
  }
  ll m = gcd(t,b);
  return {t/m,b/m};
}

frac operator+(const frac&a,const frac&b){
  return norm({a.first*b.second+a.second*b.first,a.second*b.second});
}
frac operator-(const frac&a,const frac&b){
  return norm({a.first*b.second-a.second*b.first,a.second*b.second});
}
frac operator*(const frac&a,const frac&b){
  return norm({a.first*b.first,a.second*b.second});
}

frac operator/(const frac&a,const frac&b){
  assert(b.first != 0);
  return norm({a.first*b.second,a.second*b.first});
}

pair<bool,array<frac,3> > cross(const line&l0,const line&l1){
  // pl(l0);
  // pl(l1);
  auto [p0,a0] = l0; // [x,y,z] = p0 + a0 t0
  auto [p1,a1] = l1; // [x,y,z] = p1 + a1 t1
  vector A(3,vector<frac>(3)); // 增广矩阵
  rep(i,0,3){
    A[i][0] = a0[i];
    A[i][1] = ZERO - a1[i];
    A[i][2] = p1[i]-p0[i];
  }
  // 高斯消元
  rep(c,0,2) { // col and row
    rep(i,c,3) if(A[i][c] != ZERO) {
      swap(A[i],A[c]);
      break;
    }
    if(A[c][c] == ZERO) return {false, {}};
    per(j,c,3) A[c][j] = A[c][j] / A[c][c]; // 单位化
    rep(i,0,3) if(i!=c) per(j,c,3) A[i][j] = A[i][j] - A[c][j] * A[i][c];
  }
  if(A[2][2] != ZERO) return {false,{}};
  frac t0 = A[0][2];
  frac x = p0[0] + t0 * a0[0];
  frac y = p0[1] + t0 * a0[1];
  frac z = p0[2] + t0 * a0[2];
  return {true,{x,y,z}};
}

int main(){
  vector<point> xyz;
  int n=read();
  rep(i,0,n) {
    frac x=norm({read(),1});
    frac y=norm({read(),1});
    frac z=norm({read(),1});
    xyz.push_back({x,y,z});
  }
  auto cmp= [&](auto &a,auto &b){
      rep(t,0,size(a)) if(a[t] != b[t]) return (a[t]-b[t]).second < 0;
      return false;
  };
  sort(begin(xyz),end(xyz),cmp);
  int ans = n;
  auto arrow=[&](const point&a,const point&b) -> direct {
    frac dx=b[0]-a[0];
    frac dy=b[1]-a[1];
    frac dz=b[2]-a[2];
    assert(dx != ZERO);
    dz = dz/dx;
    dy = dy/dx;
    dx = dx/dx;
    return {dx,dy,dz};
  };
  // 多点共线
  rep(i,0,n) rep(j,i+1,n) if(xyz[i][0] != xyz[j][0]){
    direct i2j = arrow(xyz[i],xyz[j]);
    int cnt = 2;
    rep(k,j+1,n) if(i2j == arrow(xyz[i],xyz[k])) cnt ++ ;
    ans = min(ans, n - (cnt-1));
  }
  auto count=[&](const point&p){
    int rm = 0;
    vector<direct> arrows;
    rep(i,0,n) arrows.push_back(arrow(p,xyz[i]));
    sort(begin(arrows),end(arrows),cmp);
    rep(i,1,size(arrows)) if(arrows[i] == arrows[i-1]) rm++;
    ans = min(ans,n-rm);
  };
  // 两线交点 i->j, k->l
  rep(i,0,n) rep(j,i+1,n) if(xyz[i][0] != xyz[j][0]) {
    line i2j = {xyz[i], arrow(xyz[i],xyz[j])};
    rep(k,i+1,n) if(k!=j) rep(l,k+1,n) if(l != j) if(xyz[k][0] != xyz[l][0]){
      line k2l = {xyz[k], arrow(xyz[k],xyz[l])};
      auto [ok, p] = cross(i2j,k2l);
      if(ok and p[0].second < 0) count(p);
    }
  }
  printf("%d\n",ans);
  return 0;
}

Ex Difference of Distance

无向n点,m边（有边权w）连通图

d(s,t) = min( s到t的路径的最重的边)

q个独立询问, 若边 ai 权重+=1, d(Si,Ti) 是否会增加

n 2e5

m 2e5

wi [1,m]

q 2e5

5s

1024mb

我的思路

首先是增加ai权重+1，那么原来的 min( s=>t) 如果没有经过 ai, 则 它不变，而 经过了ai的，如果ai不是最大值，也不会变，而经过ai且ai的权重是最大值，这条路径上才会变

所以实际的问题是:

  1. 当前d(Si,Ti) = weight[ai], 因为如果不等，更小就是有不经过它的，更大就是即使经过它它也不是最大的
  2. 是否存在一个不经过ai 且 =d(Si,Ti)的路径

并不可做

换个角度，单次直接查询呢？

那就是从S 做dij, ans[u][vis = true/false] Si到达u 是否经过边ai, 的最小代价

而实际就是看

ans[Ti][true]是否为 weight[ai]

以及

ans[Ti][false]是否为 weight[ai], (不可达记为INF, 但不可达只是说明会经过并不表示一定有贡献)

而dij 实际每次是已经到达的点 的延伸的 最小权重的边

这看上去是最小生成树

所以对询问按照 w[ai] 顺序离线处理

几个问题

虽然并查集能处理哪些点连通了，但是似乎没法做加了一条边以后哪些点连通了的通知

第二个是 增加 边a_q_i 是正常操作，但是不增加的话，需要对整个并查集复制一份， 这样空间肯定不够

第三个就是当 有很多边权重一样时 又和询问有关，如何控制顺序

对于前两问题，一个办法是

当要考虑a_i的影响时， 把所有weight <= w[ai] 的边都处理完

那么这个时候才去主动查询si,ti的关系,

  • 如果连通则说明ai不会影响

  • 如果未连通，而且ai的两头也不是si,ti对应的两个并查集，则加了ai也不连通，这样 si,ti始终会经过更大的边，也不影响

  • 只有未连通，加了ai就连通时才会影响

如果weight两两不等还好 就解决了， 如果有相等又回到第三个问题

想法是，二分法/分治，既然有 很多条 weight = w[ai]的边

那不妨把这些边放入数组 vector<int> edge

并查集拷贝一份 施加 edge 左半的链接，查询右半

并查集拷贝一份 施加 edge 右半的链接，查询左半

这样每次 (log(m) n)

而问题是当 只有2个时依然会拷贝整个，这样有拷贝就会 (m/2 n)

虽然上面解决了同一个weight，边很多时的情况

但是 反过来让边weight两两不同的情况变得复杂度过高

一个想法是在 做分治前把每个点做uf,然后拷贝内容只有这些相关的点和它们的root

然而加了一堆还是TLE

https://atcoder.jp/contests/abc301/submissions/42099268

题解

也是先判断 w[ai] = d(si,ti)

问题变成<= w[ai]图中 是否有不经过ai让si,ti相连

  • ai 在 si,ti 中是桥(删除后会使得连通块个数+1的边)，且删除ai后 两个连通块分别有si,ti

有一个lowlink算法，能O(V+E) enumerate the bridges

这个lowlink似乎就是tarjan/scc里面用的那个算法， 在这里可以找到所有bridge

而如果，一条边是桥，那么dfs遍历时，桥的子向节点是一个子(树/图)

s,t有且只有一个属于其中, 也就是 s/t \in [in[桥],out[桥]]

且在有ai的时候s,t是连通的

代码

https://atcoder.jp/contests/abc301/submissions/42102172

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
#define per(i,a,n) for (int i=n;i-->(int)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}

class UnionFind{
  public:
    vector<int> f; // f[i]
    UnionFind(int sz){ // 0-index
      f.resize(sz);
      iota(begin(f),end(f),0);
    }
    int leader(int u) { return f[u] == u ? u :f[u] = leader(f[u]); }
    void merge(int u,int v) { f[leader(u)] = leader(v); }
    bool same(int u,int v) {return leader(u) == leader(v);}
};

class lowlink {
  int n;
  vector<vector<pair<int, int>>> G;
  vector<int> in, out, low;
  unordered_map<int, int> bridge; // bridge[eid] = child vertex

  void dfs(int u, int p, int &ti) { // 计算所有low,和找桥
    in[u] = low[u] = ti++;
    for (auto [v, id]: G[u]) {
      if (in[v] == -1) {
        dfs(v, id, ti);
        low[u] = min(low[u], low[v]);
        if (low[v] > in[u]) bridge[id] = v;
      } else if (id != p) {
        low[u] = min(low[u], in[v]);
      }
    }
    out[u] = ti;
  }

  void init() {
    n = G.size();
    in.assign(n, -1);
    out.assign(n, -1);
    low.assign(n, -1);
    int ti = 0;
    rep(i,0,n) if (in[i] == -1) dfs(i, -1, ti);
  }

  public:
  lowlink(const vector<vector<pair<int, int>>> &G) : G(G) { init(); }

  bool query(int a, int s, int t) { // a是桥 且 s,t有且只有一个在 桥子节点的子(树/图)中
    assert(0 <= s and s < n);
    assert(0 <= t and t < n);
    assert(s != t);
    if (!bridge.count(a)) return false;
    int l = in[bridge[a]];
    int r = out[bridge[a]];
    s = in[s];
    t = in[t];
    return (l <= s and s < r) xor (l <= t and t < r);
  }
};

int main() {
  int n=read();
  int m=read();
  vector<int> u(m), v(m);
  vector<vector<int>> w2e(m); //
  rep(i,0,m){
    u[i]=read()-1;
    v[i]=read()-1;
    w2e[read()-1].push_back(i);
  }
  int q=read();
  vector< vector<array<int,3> > > e2stq(m);
  rep(i,0,q) {
    int eid=read()-1;
    int s  =read()-1;
    int t  =read()-1;
    e2stq[eid].push_back({s,t,i});
  }
  vector<int> ans(q, -1);
  UnionFind uf(n);
  rep(w,0,m) { // 先处理 一定不可能0
    for(int eid:w2e[w]) for(auto [s,t,qid]:e2stq[eid]) if (uf.same(s, t)) ans[qid] = 0;
    for(int eid:w2e[w]) uf.merge(u[eid], v[eid]);
    for(int eid:w2e[w]) for(auto [s,t,qid]:e2stq[eid]) if (!uf.same(s, t)) ans[qid] = 0;
  }

  uf = UnionFind(n);
  rep(w,0,m){
    // 离散化 构建小图
    vector<int> ls;
    for (int eid: w2e[w]) {
      ls.push_back(uf.leader(u[eid]));
      ls.push_back(uf.leader(v[eid]));
    }
    sort(ls.begin(), ls.end());
    ls.erase(unique(ls.begin(), ls.end()), ls.end());
    auto lb=[&](int u)->int{ return lower_bound(ls.begin(), ls.end(), uf.leader(u)) - ls.begin();};

    int sz = ls.size();
    vector<vector<pair<int, int>>> G(sz); // G[u] = array {v, edgeid}
    for (int eid: w2e[w]) if(u[eid] != v[eid]){
      int nu = lb(u[eid]);
      int nv = lb(v[eid]);
      G[nu].emplace_back(nv, eid);
      G[nv].emplace_back(nu, eid);
    }
    lowlink lk(G); // 每次构建 <= 2边, 总代价小于等于O(2m)
    for(auto eid:w2e[w]) for(auto [s,t,qid]:e2stq[eid]) if(ans[qid] == -1) {
      int ns = lb(s);
      int nt = lb(t);
      assert(ns != nt);
      assert(ns < sz and nt < sz);
      assert(ls[ns] == uf.leader(s) and ls[nt] == uf.leader(t));
      // 已经保证了 加了=w的 所有边 s,t会连通, 只需要查询eid能否让它们断开
      ans[qid] = lk.query(eid, ns, nt);
    }
    for (int eid: w2e[w]) uf.merge(u[eid], v[eid]);
  }
  rep(i,0,q) printf("%d\n", ans[i]);
  return 0;
}

总结

G

真难写,还是卡过的,甚至不知道怎么优化

Ex

一眼很难，仔细分析还是觉得比较显然

但是最后这优化还是卡住了

之前lowlink只在tarjan/scc里见过，原来它还可以用来找所有bridge

这样看起来我的并查集的办法 虽然每次复制点也是均摊总代价O(2m)，但是复制以后的合并代价会很高???

其实也是第一次做，删了一条边s,t是否连通的问题,这也是我卡住的地方

参考

官方题解