oj.uz

답안 #492467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492467 2021-12-07T13:08:29 Z Malheiros 다리 (APIO19_bridges) C++17
100 / 100
 2666 ms 11196 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ld long double
#define ll long long
//#define int ll
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
#define PB push_back
#define MP make_pair
#define all(cont) cont.begin(),cont.end()
#define rall(cont) cont.rbegin(), cont.rend()
#define FOR(i, j) for(int i=0;i<j;i++)
#define RFOR(i, j) for (int i=j;i>=0;i--)
#define GO cin.tie(NULL);
#define FAST ios_base::sync_with_stdio(false);
#define prec(x) cout << fixed << setprecision(x)
#define sz(x) (int)x.size()
 
typedef pair<int,int> pii;
typedef vector<int> VI;
typedef vector<pii> VPII;
typedef vector<VI> VVI;
typedef priority_queue<int> max_heap;
typedef priority_queue<pii> max_heapii;
typedef priority_queue<int,VI,greater<int>> min_heap;
typedef priority_queue<pii,VPII,greater<pii>> min_heapii;
 
const long double PI = 3.14159265359;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b){return uniform_int_distribution<ll>(a, b)(rng);}
 
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout<<endl;
}
 
void print(vector<int>v){
	cout<<"[";
	FOR(i,v.size()){
		cout<<v[i];
		if(i+1!=v.size())cout<<", ";
	}
	cout<<"]"<<endl;
}
 
void print(pii p){
	cout<<"{"<<p.first<<", "<<p.second<<"}"<<endl;
}
 
struct DSU{
    int* arr;
    int* size;
    stack<vector<pair<int,int>>> rb;
    int cc;
    DSU(){
 
    }
    DSU(int n){
        cc=n;
        arr = new int[n];
        for (int i=0;i<n;i++){
            arr[i]=-1;
        }
        rb.push(vector<pair<int,int>>());
    }
    int find(int a){
        while(arr[a]>=0)a=arr[a];
        return a;
    }
    void uniao(int a,int b){
        int paia=find(a);
        int paib=find(b);
        if (paia==paib)return;
        cc--;
        //paib é maior, entao liga em b
        int tam=arr[paia]+arr[paib];
        if (arr[paia]>arr[paib]){
            rb.top().push_back({paib,arr[paib]});
            rb.top().push_back({paia,arr[paia]});
            arr[paia]=paib;
            arr[paib]=tam;
        }
        else{
            rb.top().push_back({paib,arr[paib]});
            rb.top().push_back({paia,arr[paia]});
            arr[paib]=paia;
            arr[paia]=tam;
        }
    }
    void persist(){
        rb.push(vector<pair<int,int>>());
    }
    void rollback(){
        auto changes=rb.top();
        rb.pop();
        int n=changes.size();
        cc+=n/2;
        for (int i=n-1;i>=0;i--){
            arr[changes[i].first]=changes[i].second;
        }
    }
};
 
 
const int maxn=1e5+10;
const int magic=800;  
int ord[maxn];
int ans[maxn];
int n,m;
vector<pair<int,pii>> bridges;//{weight,{a,b}};
vector<pair<int,pii>> updates[magic];//{tempo,{qual,peso}};
vector<pair<int,pii>> queries[magic];//{peso,{tempo,qual}};
DSU dsu;
int mrds[maxn];
int mudanca[maxn];
void solve(int u,pair<int,pii> q){
  int it=0;
  VI mudei;
  while(it<sz(updates[u]) && updates[u][it].first<q.SF){
    mudanca[updates[u][it].SF]=updates[u][it].SS;
    mudei.PB(updates[u][it].SF);
    it++;
  }
  for(auto k1:updates[u]){
    auto k=k1.SF;
    if (mudanca[k]==0){
      if (bridges[k].first>=q.first){
        //deb(bridges[k].SS,bridges[k].SF);
        dsu.uniao(bridges[k].SS,bridges[k].SF);
      }
    }
    else{
      if (mudanca[k]>=q.first){
        //deb(bridges[k].SS,bridges[k].SF);
        dsu.uniao(bridges[k].SS,bridges[k].SF);
      }
    }
  }
  for(auto k:mudei) mudanca[k]=0;
  //deb(ord[q.SF]);
  ans[ord[q.SF]]=-dsu.arr[dsu.find(q.SS)];
}
 
void solve(int u){
  //deb(n,dsu.cc);
  for(auto k:updates[u]) mrds[k.SF]=1;
  vector<pii> unchanged;
  FOR(i,m){
    if (!mrds[i])unchanged.PB({bridges[i].first,i});
  }
  sort(rall(unchanged));
  sort(rall(queries[u]));
  auto it=0;
  dsu.persist();
  for(auto q:queries[u]){
    while(it<sz(unchanged)){
      if (unchanged[it].first>=q.first){
        //deb(bridges[it->second].SF,bridges[it->second].SS);
        dsu.uniao(bridges[unchanged[it].second].SF,bridges[unchanged[it].second].SS);
        it++;
      }
      else break;
    }
    //cout<<"PERSISTINDO"<<endl;
    dsu.persist();
    solve(u,q);
    //cout<<"ROLLBACK"<<endl;
    dsu.rollback();
  }
  dsu.rollback();
  for(auto k:updates[u]){
    mrds[k.SF]=0;
    bridges[k.SF].first=k.SS;
  }
}
 
signed main(){
  GO FAST
  cin>>n>>m;
  dsu=DSU(n);
  bridges=vector<pair<int,pii>>(m);
  FOR(i,m){
    int a,b,c;cin>>a>>b>>c;a--;b--;
    bridges[i]={c,{a,b}};
  }
  int q;cin>>q;
  int cont=0;
  FOR(i,q){
    int a,b,c;cin>>a>>b>>c;
    b--;
    if (a==1){//update
      updates[i/magic].push_back({i,{b,c}});
    }
    else{
        queries[i/magic].push_back({c,{i,b}});
        ord[i]=cont++;
    }
  }
  FOR(i,magic)if((!queries[i].empty()) ||  (!updates[i].empty()))solve(i);
  FOR(i,cont){
    cout<<ans[i]<<'\n';
  }
}

Compilation message

bridges.cpp: In function 'void print(std::vector<int>)':
bridges.cpp:16:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define FOR(i, j) for(int i=0;i<j;i++)
......
   47 |  FOR(i,v.size()){
      |      ~~~~~~~~~~                 
bridges.cpp:47:2: note: in expansion of macro 'FOR'
   47 |  FOR(i,v.size()){
      |  ^~~
bridges.cpp:49:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   if(i+1!=v.size())cout<<", ";
      |      ~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 35 ms 588 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 43 ms 588 KB Output is correct
6 Correct 31 ms 596 KB Output is correct
7 Correct 37 ms 596 KB Output is correct
8 Correct 40 ms 612 KB Output is correct
9 Correct 45 ms 584 KB Output is correct
10 Correct 46 ms 608 KB Output is correct
11 Correct 46 ms 620 KB Output is correct
12 Correct 47 ms 588 KB Output is correct
13 Correct 46 ms 616 KB Output is correct
14 Correct 45 ms 632 KB Output is correct
15 Correct 45 ms 616 KB Output is correct
16 Correct 50 ms 604 KB Output is correct
17 Correct 49 ms 588 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1535 ms 6716 KB Output is correct
2 Correct 1659 ms 6652 KB Output is correct
3 Correct 1565 ms 6644 KB Output is correct
4 Correct 1585 ms 6896 KB Output is correct
5 Correct 1614 ms 6760 KB Output is correct
6 Correct 2095 ms 6648 KB Output is correct
7 Correct 2036 ms 6608 KB Output is correct
8 Correct 2067 ms 6708 KB Output is correct
9 Correct 32 ms 2808 KB Output is correct
10 Correct 1511 ms 8428 KB Output is correct
11 Correct 1443 ms 8384 KB Output is correct
12 Correct 1402 ms 9524 KB Output is correct
13 Correct 1411 ms 9500 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1207 ms 5160 KB Output is correct
2 Correct 811 ms 3108 KB Output is correct
3 Correct 1358 ms 5048 KB Output is correct
4 Correct 1186 ms 5040 KB Output is correct
5 Correct 33 ms 2756 KB Output is correct
6 Correct 1293 ms 7312 KB Output is correct
7 Correct 1111 ms 7504 KB Output is correct
8 Correct 1008 ms 7440 KB Output is correct
9 Correct 904 ms 7744 KB Output is correct
10 Correct 901 ms 7708 KB Output is correct
11 Correct 952 ms 7364 KB Output is correct
12 Correct 868 ms 7408 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2029 ms 6636 KB Output is correct
2 Correct 33 ms 4164 KB Output is correct
3 Correct 190 ms 5512 KB Output is correct
4 Correct 125 ms 5556 KB Output is correct
5 Correct 2001 ms 8884 KB Output is correct
6 Correct 2032 ms 10440 KB Output is correct
7 Correct 2031 ms 8880 KB Output is correct
8 Correct 1026 ms 9080 KB Output is correct
9 Correct 999 ms 9252 KB Output is correct
10 Correct 1035 ms 8952 KB Output is correct
11 Correct 1526 ms 9372 KB Output is correct
12 Correct 1538 ms 9608 KB Output is correct
13 Correct 1496 ms 9180 KB Output is correct
14 Correct 1742 ms 8936 KB Output is correct
15 Correct 1829 ms 8884 KB Output is correct
16 Correct 1991 ms 10336 KB Output is correct
17 Correct 1944 ms 10308 KB Output is correct
18 Correct 1953 ms 10508 KB Output is correct
19 Correct 2019 ms 10424 KB Output is correct
20 Correct 1658 ms 9448 KB Output is correct
21 Correct 1633 ms 9404 KB Output is correct
22 Correct 1880 ms 10148 KB Output is correct
23 Correct 1721 ms 8180 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1535 ms 6716 KB Output is correct
2 Correct 1659 ms 6652 KB Output is correct
3 Correct 1565 ms 6644 KB Output is correct
4 Correct 1585 ms 6896 KB Output is correct
5 Correct 1614 ms 6760 KB Output is correct
6 Correct 2095 ms 6648 KB Output is correct
7 Correct 2036 ms 6608 KB Output is correct
8 Correct 2067 ms 6708 KB Output is correct
9 Correct 32 ms 2808 KB Output is correct
10 Correct 1511 ms 8428 KB Output is correct
11 Correct 1443 ms 8384 KB Output is correct
12 Correct 1402 ms 9524 KB Output is correct
13 Correct 1411 ms 9500 KB Output is correct
14 Correct 1207 ms 5160 KB Output is correct
15 Correct 811 ms 3108 KB Output is correct
16 Correct 1358 ms 5048 KB Output is correct
17 Correct 1186 ms 5040 KB Output is correct
18 Correct 33 ms 2756 KB Output is correct
19 Correct 1293 ms 7312 KB Output is correct
20 Correct 1111 ms 7504 KB Output is correct
21 Correct 1008 ms 7440 KB Output is correct
22 Correct 904 ms 7744 KB Output is correct
23 Correct 901 ms 7708 KB Output is correct
24 Correct 952 ms 7364 KB Output is correct
25 Correct 868 ms 7408 KB Output is correct
26 Correct 1495 ms 9396 KB Output is correct
27 Correct 1816 ms 9260 KB Output is correct
28 Correct 1656 ms 9428 KB Output is correct
29 Correct 1336 ms 9632 KB Output is correct
30 Correct 1771 ms 9280 KB Output is correct
31 Correct 1799 ms 9236 KB Output is correct
32 Correct 1841 ms 9300 KB Output is correct
33 Correct 1656 ms 9436 KB Output is correct
34 Correct 1615 ms 9512 KB Output is correct
35 Correct 1660 ms 9452 KB Output is correct
36 Correct 1304 ms 9480 KB Output is correct
37 Correct 1368 ms 9348 KB Output is correct
38 Correct 1310 ms 9524 KB Output is correct
39 Correct 1152 ms 9796 KB Output is correct
40 Correct 1126 ms 9760 KB Output is correct
41 Correct 1160 ms 9916 KB Output is correct
42 Correct 1087 ms 9396 KB Output is correct
43 Correct 1122 ms 9456 KB Output is correct
44 Correct 1133 ms 9620 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 35 ms 588 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 43 ms 588 KB Output is correct
6 Correct 31 ms 596 KB Output is correct
7 Correct 37 ms 596 KB Output is correct
8 Correct 40 ms 612 KB Output is correct
9 Correct 45 ms 584 KB Output is correct
10 Correct 46 ms 608 KB Output is correct
11 Correct 46 ms 620 KB Output is correct
12 Correct 47 ms 588 KB Output is correct
13 Correct 46 ms 616 KB Output is correct
14 Correct 45 ms 632 KB Output is correct
15 Correct 45 ms 616 KB Output is correct
16 Correct 50 ms 604 KB Output is correct
17 Correct 49 ms 588 KB Output is correct
18 Correct 1535 ms 6716 KB Output is correct
19 Correct 1659 ms 6652 KB Output is correct
20 Correct 1565 ms 6644 KB Output is correct
21 Correct 1585 ms 6896 KB Output is correct
22 Correct 1614 ms 6760 KB Output is correct
23 Correct 2095 ms 6648 KB Output is correct
24 Correct 2036 ms 6608 KB Output is correct
25 Correct 2067 ms 6708 KB Output is correct
26 Correct 32 ms 2808 KB Output is correct
27 Correct 1511 ms 8428 KB Output is correct
28 Correct 1443 ms 8384 KB Output is correct
29 Correct 1402 ms 9524 KB Output is correct
30 Correct 1411 ms 9500 KB Output is correct
31 Correct 1207 ms 5160 KB Output is correct
32 Correct 811 ms 3108 KB Output is correct
33 Correct 1358 ms 5048 KB Output is correct
34 Correct 1186 ms 5040 KB Output is correct
35 Correct 33 ms 2756 KB Output is correct
36 Correct 1293 ms 7312 KB Output is correct
37 Correct 1111 ms 7504 KB Output is correct
38 Correct 1008 ms 7440 KB Output is correct
39 Correct 904 ms 7744 KB Output is correct
40 Correct 901 ms 7708 KB Output is correct
41 Correct 952 ms 7364 KB Output is correct
42 Correct 868 ms 7408 KB Output is correct
43 Correct 2029 ms 6636 KB Output is correct
44 Correct 33 ms 4164 KB Output is correct
45 Correct 190 ms 5512 KB Output is correct
46 Correct 125 ms 5556 KB Output is correct
47 Correct 2001 ms 8884 KB Output is correct
48 Correct 2032 ms 10440 KB Output is correct
49 Correct 2031 ms 8880 KB Output is correct
50 Correct 1026 ms 9080 KB Output is correct
51 Correct 999 ms 9252 KB Output is correct
52 Correct 1035 ms 8952 KB Output is correct
53 Correct 1526 ms 9372 KB Output is correct
54 Correct 1538 ms 9608 KB Output is correct
55 Correct 1496 ms 9180 KB Output is correct
56 Correct 1742 ms 8936 KB Output is correct
57 Correct 1829 ms 8884 KB Output is correct
58 Correct 1991 ms 10336 KB Output is correct
59 Correct 1944 ms 10308 KB Output is correct
60 Correct 1953 ms 10508 KB Output is correct
61 Correct 2019 ms 10424 KB Output is correct
62 Correct 1658 ms 9448 KB Output is correct
63 Correct 1633 ms 9404 KB Output is correct
64 Correct 1880 ms 10148 KB Output is correct
65 Correct 1721 ms 8180 KB Output is correct
66 Correct 1495 ms 9396 KB Output is correct
67 Correct 1816 ms 9260 KB Output is correct
68 Correct 1656 ms 9428 KB Output is correct
69 Correct 1336 ms 9632 KB Output is correct
70 Correct 1771 ms 9280 KB Output is correct
71 Correct 1799 ms 9236 KB Output is correct
72 Correct 1841 ms 9300 KB Output is correct
73 Correct 1656 ms 9436 KB Output is correct
74 Correct 1615 ms 9512 KB Output is correct
75 Correct 1660 ms 9452 KB Output is correct
76 Correct 1304 ms 9480 KB Output is correct
77 Correct 1368 ms 9348 KB Output is correct
78 Correct 1310 ms 9524 KB Output is correct
79 Correct 1152 ms 9796 KB Output is correct
80 Correct 1126 ms 9760 KB Output is correct
81 Correct 1160 ms 9916 KB Output is correct
82 Correct 1087 ms 9396 KB Output is correct
83 Correct 1122 ms 9456 KB Output is correct
84 Correct 1133 ms 9620 KB Output is correct
85 Correct 2416 ms 11032 KB Output is correct
86 Correct 227 ms 6264 KB Output is correct
87 Correct 172 ms 6316 KB Output is correct
88 Correct 2251 ms 9516 KB Output is correct
89 Correct 2394 ms 11032 KB Output is correct
90 Correct 2299 ms 9120 KB Output is correct
91 Correct 1805 ms 9308 KB Output is correct
92 Correct 1656 ms 9540 KB Output is correct
93 Correct 2119 ms 9260 KB Output is correct
94 Correct 2044 ms 9712 KB Output is correct
95 Correct 1941 ms 9860 KB Output is correct
96 Correct 2386 ms 9584 KB Output is correct
97 Correct 2052 ms 9568 KB Output is correct
98 Correct 2180 ms 9200 KB Output is correct
99 Correct 2558 ms 10960 KB Output is correct
100 Correct 2448 ms 10932 KB Output is correct
101 Correct 2454 ms 11196 KB Output is correct
102 Correct 2410 ms 11036 KB Output is correct
103 Correct 2384 ms 9876 KB Output is correct
104 Correct 2405 ms 9764 KB Output is correct
105 Correct 1964 ms 9912 KB Output is correct
106 Correct 1577 ms 9508 KB Output is correct
107 Correct 1830 ms 10092 KB Output is correct
108 Correct 2666 ms 10296 KB Output is correct
109 Correct 2360 ms 8400 KB Output is correct