Submission #202642

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
202642	2020-02-17 13:14:22	dennisstar	Bridges (APIO19_bridges)	C++17	44 / 100	3057 ms	16176 KiB

bridges

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
#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef vector<int> vim;
typedef pair<int, int> pii;
const int B = 800;
struct line {
  int u, v, r;
  line(int U, int V, int R) : u(U), v(V), r(R) {}
};
typedef shared_ptr<vector<line> > pvii;
struct UF {
  vim par, rnk, sz, cp; vector<pii> cr;
  UF(int n) : par(n+1, 0), rnk(n+1, 0), sz(n+1, 1) {}
  int get(int x) { return par[x]?get(par[x]):x; }
  bool Union(int x, int y) {
    x=get(x), y=get(y);
    if (x==y) return false;
    if (rnk[x]<rnk[y]) swap(x, y);
    cp.eb(y); cr.eb(x, rnk[x]);
    par[y]=x; rnk[x]=max(rnk[x], rnk[y]+1); sz[x]+=sz[y];
    return true;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

bridges.cpp: In function 'void solve(int, std::vector<line>, std::vector<std::pair<qu, std::shared_ptr<std::vector<line> > > >)':
bridges.cpp:52:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (fr<Fix.size()&&Fix[fr].r>=i.fi.rs) U.Union(Fix[fr].u, Fix[fr].v), fr++;
          ~~^~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:60:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M, Q; scanf("%d %d", &N, &M);
               ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp:64:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &r), L.eb(u, v, r);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
bridges.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
bridges.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &q[i], &b[i], &r[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27