제출 #249133

#제출 시각아이디문제언어결과실행 시간메모리
249133crossing0ver다리 (APIO19_bridges)C++17
0 / 100
3078 ms524292 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; const int N = 5e4+5; struct bridge{ int a,b,val; bridge(){ a = b = val = 0; } }; int n,m,q; bool vis[N]; vector<bridge> e; vector< pair<int,int> > adj[N]; int dfs(int v,int val) { int cnt = 1; vis[v] = 1; for (auto i : adj[v]) { if (i.second >= val && !vis[i.first]) cnt += dfs(i.first,val); } return cnt; } int arr[100009],t[400009]; void build(int v,int tl,int tr) { if (tl == tr) { t[v] = arr[tl]; return; } int tm = (tl + tr)/2; build(v*2,tl,tm); build(v*2|1,tm+1,tr); t[v] = min(t[v*2],t[v*2+1]); } void upd(int v,int tl,int tr,int pos,int val) { if (tl == tr) { t[v] = arr[tl] = val; return; } int tm = (tl + tr)/2; if (pos <= tm) upd(v*2,tl,tm,pos,val); else upd(v*2|1,tm+1,tr,pos,val); t[v] = min(t[v*2],t[v*2+1]); } int get(int v,int tl,int tr,int l,int r) { if (l > tr || r < tl) return INT_MAX; if (l <= tl && r >= tr) return t[v]; int tm = (tl + tr)/2; return min( get(v*2,tl,tm,l,r), get(v*2|1,tm+1,tr,l,r)); } void LINE() { for (int i = 1; i <= m; i++) { arr[i] = e[i].val; } build(1,1,m); for (int type,x,y;q--;) { cin >> type >> x >> y; if (type == 1) { upd(1,1,m,x,y); } else { // cout << dfs(x,y) <<'\n'; int lo = x-1, hi = m; while (lo < hi) { int mid = (lo + hi + 1)/2; if (get(1,1,m,x,mid) >= y) lo = mid; else hi = mid-1; } int ans = 1; ans = lo + 1 - x; lo = 0, hi = x-1; while (lo < hi) { int mid = (lo + hi)/2; if (get(1,1,m,mid,x-1) >= y) hi = mid; else lo = mid+1; } if (hi == 0 || get(1,1,m,x,hi) < y) hi++; ans += x - hi; cout << ans <<'\n'; } } exit(0); } main() { cin >> n >> m; e.resize(m+1); bool fl1 = (m == n-1); for (int i = 1; i <= m; i++) { cin >> e[i].a >> e[i].b >> e[i].val; if (e[i].a != i || e[i].b != i+1) fl1 = 0; adj[e[i].a].pb({e[i].b,e[i].val}); adj[e[i].b].pb({e[i].a,e[i].val}); } cin >> q; if (fl1) { LINE(); } for (int type,x,y;q--;) { cin >> type >> x >> y; if (type == 1) { int a = e[x].a, b = e[x].b,val = e[x].val; adj[a].erase(find(adj[a].begin(),adj[a].end(),make_pair(b,val))); adj[b].erase(find(adj[b].begin(),adj[b].end(),make_pair(a,val))); e[x].val = y; adj[a].pb({b,y}); adj[b].pb({a,y}); } else { cout << dfs(x,y) <<'\n'; fill(vis,vis+n+1,0); } } }

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...