Submission #1071087

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1071087	2024-08-23 04:21:03	kustizus	Bridges (APIO19_bridges)	C++17	100 / 100	2484 ms	9208 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
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
// #define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1e5;
int n,m,q,u[N+5],v[N+5],d[N+5],ty[N+5],x[N+5],y[N+5],ans[N+5],tr[N+5];
bool ok,use[N+5];
void Update(int i, int j){
    for (int k=i;k<=j;++k)
        if (ty[k]==1) d[x[k]]=y[k];
}
struct DSU_rollback{
    int ds[N+5];
    vector <pair<int,int>> history;
    void Reset(){
        for (int i=1;i<=n;++i) ds[i]=-1;
        history.clear();
    }
    int Get(int idx){
        return ds[idx]<0 ? idx : Get(ds[idx]);
    }
    void Join(int u, int v){
        u=Get(u);
        v=Get(v);
        if (u==v) return;
        if (ds[u]>ds[v]) swap(u,v);
        if (ok) history.push_back({v,ds[v]});
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

bridges.cpp: In member function 'void DSU_rollback::RollBack(int)':
bridges.cpp:35:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         while (history.size()>sz){
      |                ~~~~~~~~~~~~~~^~~
bridges.cpp: In function 'void Sol(int, int)':
bridges.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (pointer<before_edge.size() && d[before_edge[pointer]]>=y[pos]){
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~

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