# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
960161 | 2024-04-09T18:50:09 Z | hariaakas646 | Bridges (APIO19_bridges) | C++14 | 3000 ms | 7708 KB |
#include <bits/stdc++.h> using namespace std; #define scd(t) scanf("%d", &t) #define sclld(t) scanf("%lld", &t) #define forr(i, j, k) for (int i = j; i < k; i++) #define frange(i, j) forr(i, 0, j) #define all(cont) cont.begin(), cont.end() #define mp make_pair #define pb push_back #define f first #define s second typedef long long int lli; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<lli> vll; typedef vector<string> vs; typedef vector<pii> vii; typedef vector<vi> vvi; typedef map<int, int> mpii; typedef set<int> seti; typedef multiset<int> mseti; typedef long double ld; void usaco() { freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin); // freopen("problem.out", "w", stdout); } vi disset, sze, cnt, out; stack<pii> stk; int n, m; int findf(int x) { while(x != disset[x]) { x = disset[x]; } return x; } void unionf(int u, int v) { u = findf(u); v = findf(v); if(u == v) return; if(sze[u] > sze[v]) swap(u, v); disset[u] = v; sze[v] = max(sze[v], sze[u]+1); stk.push(mp(u, v)); cnt[v] += cnt[u]; } vector<pair<int, pii>> edge; void process(vector<pair<pii, pii>> quer) { vb change(m); stk = {}; vector<pair<pii, int>> calc; vector<pair<pii, int>> upd; vvi uped(m); disset = vi(n+1); forr(i, 1, n+1) disset[i] = i; sze = cnt= vi(n+1, 1); for(auto p : quer) { if(p.f.s == 1) { // printf("%d\n", p.s.s); change[p.s.s] = true; upd.pb(mp(p.s, p.f.f)); uped[p.s.s].pb(p.f.f); } else calc.pb(mp(p.s, p.f.f)); } // upd.pb(mp(mp(0, 0), 1e6)); sort(all(calc), greater<>()); vector<pair<int, pii>> st; frange(i, m) { auto p = edge[i]; if(!change[i]) st.pb(p); } sort(all(st)); // printf("upd:\n"); // for(auto p1 : upd) { // printf("%d %d\n", edge[p1.f.s].s.f, edge[p1.f.s].s.s); // } // printf("std:\n"); // for(auto p1 : st) { // printf("%d %d\n", p1.s.f, p1.s.s); // } int it = st.size(); vi idx(m); for(auto p : calc) { // printf("%d:\n", p.s); stk = {}; frange(i, upd.size()) { auto p1 = upd[i]; int v = edge[p1.f.s].f; auto it = idx[p1.f.s]; idx[p1.f.s]++; if(p1.s < p.s) v = p1.f.f; else if(it > 0) continue; if(it+1 != uped[p1.f.s].size() && uped[p1.f.s][it+1] < p.s) continue; if(v >= p.f.f) { unionf(edge[p1.f.s].s.f, edge[p1.f.s].s.s); // printf("upd %d %d\n", edge[p1.f.s].s.f, edge[p1.f.s].s.s); } } frange(i, upd.size()) { auto p1 = upd[i]; idx[p1.f.s] = 0; } auto it1 = it; while(it != 0 && st[it-1].f >= p.f.f) { it--; auto p1 = st[it]; unionf(p1.s.f, p1.s.s); // printf("std %d %d\n", p1.s.f, p1.s.s); } out[p.s] = cnt[findf(p.f.s)]; while(stk.size()) { auto p1 = stk.top(); stk.pop(); disset[p1.f] = p1.f; cnt[p1.s] -= cnt[p1.f]; } it = it1; while(it != 0 && st[it-1].f >= p.f.f) { it--; auto p1 = st[it]; unionf(p1.s.f, p1.s.s); } } for(auto p : upd) { edge[p.f.s].f = p.f.f; } } int main() { // usaco(); scd(n); scd(m); edge = vector<pair<int, pii>>(m); frange(i, m) { scd(edge[i].s.f); scd(edge[i].s.s); scd(edge[i].f); } int q; scd(q); int sq = sqrt(q); vector<pair<pii, pii>> quer; out = vi(q, -1); frange(i, q) { pair<pii, pii> p; p.f.f = i; scd(p.f.s); scd(p.s.s); scd(p.s.f); if(p.f.s == 1) p.s.s--; quer.pb(p); if(quer.size() >= sq) { process(quer); quer = {}; } } process(quer); for(auto e : out) if(e != -1) {printf("%d\n", e);} }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 15 ms | 540 KB | Output is correct |
4 | Correct | 4 ms | 348 KB | Output is correct |
5 | Correct | 7 ms | 484 KB | Output is correct |
6 | Correct | 6 ms | 344 KB | Output is correct |
7 | Correct | 7 ms | 348 KB | Output is correct |
8 | Correct | 8 ms | 344 KB | Output is correct |
9 | Correct | 7 ms | 344 KB | Output is correct |
10 | Correct | 8 ms | 348 KB | Output is correct |
11 | Correct | 7 ms | 348 KB | Output is correct |
12 | Correct | 8 ms | 348 KB | Output is correct |
13 | Correct | 9 ms | 492 KB | Output is correct |
14 | Correct | 8 ms | 344 KB | Output is correct |
15 | Correct | 8 ms | 348 KB | Output is correct |
16 | Correct | 7 ms | 484 KB | Output is correct |
17 | Correct | 8 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1886 ms | 4864 KB | Output is correct |
2 | Correct | 1896 ms | 4776 KB | Output is correct |
3 | Correct | 1904 ms | 4768 KB | Output is correct |
4 | Correct | 1909 ms | 4812 KB | Output is correct |
5 | Correct | 1920 ms | 5036 KB | Output is correct |
6 | Correct | 1979 ms | 5432 KB | Output is correct |
7 | Correct | 1988 ms | 5072 KB | Output is correct |
8 | Correct | 1996 ms | 5068 KB | Output is correct |
9 | Correct | 34 ms | 856 KB | Output is correct |
10 | Correct | 1678 ms | 4964 KB | Output is correct |
11 | Correct | 1747 ms | 4960 KB | Output is correct |
12 | Correct | 1855 ms | 5240 KB | Output is correct |
13 | Correct | 1860 ms | 5052 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1341 ms | 3272 KB | Output is correct |
2 | Correct | 443 ms | 1476 KB | Output is correct |
3 | Correct | 1345 ms | 3788 KB | Output is correct |
4 | Correct | 1307 ms | 3360 KB | Output is correct |
5 | Correct | 33 ms | 860 KB | Output is correct |
6 | Correct | 1323 ms | 3528 KB | Output is correct |
7 | Correct | 1299 ms | 3376 KB | Output is correct |
8 | Correct | 1282 ms | 3476 KB | Output is correct |
9 | Correct | 1203 ms | 3980 KB | Output is correct |
10 | Correct | 1222 ms | 4012 KB | Output is correct |
11 | Correct | 1236 ms | 3380 KB | Output is correct |
12 | Correct | 1202 ms | 3528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3097 ms | 7708 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1886 ms | 4864 KB | Output is correct |
2 | Correct | 1896 ms | 4776 KB | Output is correct |
3 | Correct | 1904 ms | 4768 KB | Output is correct |
4 | Correct | 1909 ms | 4812 KB | Output is correct |
5 | Correct | 1920 ms | 5036 KB | Output is correct |
6 | Correct | 1979 ms | 5432 KB | Output is correct |
7 | Correct | 1988 ms | 5072 KB | Output is correct |
8 | Correct | 1996 ms | 5068 KB | Output is correct |
9 | Correct | 34 ms | 856 KB | Output is correct |
10 | Correct | 1678 ms | 4964 KB | Output is correct |
11 | Correct | 1747 ms | 4960 KB | Output is correct |
12 | Correct | 1855 ms | 5240 KB | Output is correct |
13 | Correct | 1860 ms | 5052 KB | Output is correct |
14 | Correct | 1341 ms | 3272 KB | Output is correct |
15 | Correct | 443 ms | 1476 KB | Output is correct |
16 | Correct | 1345 ms | 3788 KB | Output is correct |
17 | Correct | 1307 ms | 3360 KB | Output is correct |
18 | Correct | 33 ms | 860 KB | Output is correct |
19 | Correct | 1323 ms | 3528 KB | Output is correct |
20 | Correct | 1299 ms | 3376 KB | Output is correct |
21 | Correct | 1282 ms | 3476 KB | Output is correct |
22 | Correct | 1203 ms | 3980 KB | Output is correct |
23 | Correct | 1222 ms | 4012 KB | Output is correct |
24 | Correct | 1236 ms | 3380 KB | Output is correct |
25 | Correct | 1202 ms | 3528 KB | Output is correct |
26 | Correct | 2132 ms | 4864 KB | Output is correct |
27 | Correct | 2204 ms | 4848 KB | Output is correct |
28 | Correct | 2168 ms | 4584 KB | Output is correct |
29 | Correct | 2064 ms | 4808 KB | Output is correct |
30 | Correct | 2072 ms | 4964 KB | Output is correct |
31 | Correct | 2113 ms | 4780 KB | Output is correct |
32 | Correct | 2122 ms | 4972 KB | Output is correct |
33 | Correct | 2041 ms | 4780 KB | Output is correct |
34 | Correct | 2044 ms | 5028 KB | Output is correct |
35 | Correct | 2050 ms | 4868 KB | Output is correct |
36 | Correct | 1982 ms | 4916 KB | Output is correct |
37 | Correct | 2013 ms | 4964 KB | Output is correct |
38 | Correct | 2005 ms | 4912 KB | Output is correct |
39 | Correct | 1926 ms | 4976 KB | Output is correct |
40 | Correct | 1923 ms | 4912 KB | Output is correct |
41 | Correct | 1933 ms | 4972 KB | Output is correct |
42 | Correct | 1816 ms | 5132 KB | Output is correct |
43 | Correct | 1836 ms | 4868 KB | Output is correct |
44 | Correct | 1839 ms | 4904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 15 ms | 540 KB | Output is correct |
4 | Correct | 4 ms | 348 KB | Output is correct |
5 | Correct | 7 ms | 484 KB | Output is correct |
6 | Correct | 6 ms | 344 KB | Output is correct |
7 | Correct | 7 ms | 348 KB | Output is correct |
8 | Correct | 8 ms | 344 KB | Output is correct |
9 | Correct | 7 ms | 344 KB | Output is correct |
10 | Correct | 8 ms | 348 KB | Output is correct |
11 | Correct | 7 ms | 348 KB | Output is correct |
12 | Correct | 8 ms | 348 KB | Output is correct |
13 | Correct | 9 ms | 492 KB | Output is correct |
14 | Correct | 8 ms | 344 KB | Output is correct |
15 | Correct | 8 ms | 348 KB | Output is correct |
16 | Correct | 7 ms | 484 KB | Output is correct |
17 | Correct | 8 ms | 376 KB | Output is correct |
18 | Correct | 1886 ms | 4864 KB | Output is correct |
19 | Correct | 1896 ms | 4776 KB | Output is correct |
20 | Correct | 1904 ms | 4768 KB | Output is correct |
21 | Correct | 1909 ms | 4812 KB | Output is correct |
22 | Correct | 1920 ms | 5036 KB | Output is correct |
23 | Correct | 1979 ms | 5432 KB | Output is correct |
24 | Correct | 1988 ms | 5072 KB | Output is correct |
25 | Correct | 1996 ms | 5068 KB | Output is correct |
26 | Correct | 34 ms | 856 KB | Output is correct |
27 | Correct | 1678 ms | 4964 KB | Output is correct |
28 | Correct | 1747 ms | 4960 KB | Output is correct |
29 | Correct | 1855 ms | 5240 KB | Output is correct |
30 | Correct | 1860 ms | 5052 KB | Output is correct |
31 | Correct | 1341 ms | 3272 KB | Output is correct |
32 | Correct | 443 ms | 1476 KB | Output is correct |
33 | Correct | 1345 ms | 3788 KB | Output is correct |
34 | Correct | 1307 ms | 3360 KB | Output is correct |
35 | Correct | 33 ms | 860 KB | Output is correct |
36 | Correct | 1323 ms | 3528 KB | Output is correct |
37 | Correct | 1299 ms | 3376 KB | Output is correct |
38 | Correct | 1282 ms | 3476 KB | Output is correct |
39 | Correct | 1203 ms | 3980 KB | Output is correct |
40 | Correct | 1222 ms | 4012 KB | Output is correct |
41 | Correct | 1236 ms | 3380 KB | Output is correct |
42 | Correct | 1202 ms | 3528 KB | Output is correct |
43 | Execution timed out | 3097 ms | 7708 KB | Time limit exceeded |
44 | Halted | 0 ms | 0 KB | - |