oj.uz

Submission #968722

# Submission time Handle Problem Language Result Execution time Memory
968722 2024-04-23T23:36:46 Z idiotcomputer Bridges (APIO19_bridges) C++11
59 / 100
 3000 ms 4880 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second 
#define pb push_back
#define sz size 
 
const int mxN = 1e5;
 
struct edge {
    int a,b,w;
};
 
edge edges[mxN];
edge all[mxN];
int p[mxN];
int ssize[mxN];
int cnt[mxN];
int gsize;
stack<int> upd;
 
bool comp(int a, int b){
    return (edges[a].w > edges[b].w);
}
 
bool comp2(int a, int b){
    return all[a].w > all[b].w;
}
 
int gp(int a){
    while (p[a] != a) a = p[a];
    return a;
}

void group(int u, int v){
    u = gp(u);
    v = gp(v);
    if (u==v) return;
    if (ssize[u] < ssize[v]) swap(u,v);
    ssize[u] += ssize[v];
    p[v] = u;
    upd.push(v);
    return;
}
 
void reset(int a){
    int c;
    while (upd.sz() > a){
        c = upd.top();
        upd.pop();
        ssize[p[c]] -= ssize[c];
        p[c] = c;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(cnt,0,sizeof(cnt));
 
    int n,m;
    cin >> n >> m;
    
    for (int i =0; i < m; i++){
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
        edges[i].a -= 1;
        edges[i].b -= 1;
    }
    
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        cin >> all[i].a >> all[i].b >> all[i].w;
        all[i].b -= 1;
    }
    for (int i =0; i < n; i++){
        p[i] = i;
        ssize[i] = 1;
    }
    gsize = sqrt(q);
    vector<int> curre;
    vector<int> cvis;
    vector<int> ans;
    int cidx;
    int res[q];
    for (int i =0; i < q; i++) res[i] = -1;
  //  cout <<"GISZE " <<  gsize << "\n";
    for (int i =0; i < (int) ceil((double) q/gsize); i++){
        curre.clear();
        ans.clear();
        cvis.clear();
       /* cout << "W: ";
        for (int j = 0; j < m; j++) cout << edges[j].w << " ";
        cout << '\n';*/
        for (int j = min(q,(i+1)*gsize)-1; j >= i*gsize; j--){
            if (all[j].a == 1 && cnt[all[j].b] != i+1){
                cnt[all[j].b] = i+1;
                cvis.pb(j);
            } else {
                ans.pb(j);
            }
        }
        for (int j = 0; j < m; j++) if (cnt[j] != i+1) curre.pb(j);
        sort(curre.begin(),curre.end(),comp);
        sort(ans.begin(),ans.end(),comp2);
       /*cout << i << ":\n";
        for (int j : curre) cout << j << " ";
        cout << '\n';
        for (int j : ans) cout << j << " ";
        cout << "\n";*/
        
        cidx = 0;
        int u,v;
        for (int j = 0; j < ans.sz(); j++){
            //Adding on non-changing edges
         //   cout << j <<" - "; 
            while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
           //    cout << curre[cidx] << " ";
                group(edges[curre[cidx]].a,edges[curre[cidx]].b);
                cidx++;
            }
            int osize = upd.sz();
      //      cout << " 2 ";
            for (int k = ans[j]-1; k >= i*gsize; k--){
                if (all[k].a == 2 || cnt[all[k].b] == q+i+1) continue;
                cnt[all[k].b] = q+i+1;
                if (all[k].w < all[ans[j]].w) continue;
                //    cout << all[k].b << " ";
                group(edges[all[k].b].a,edges[all[k].b].b);
            }
       //     cout << " 3 ";
            for (int k : cvis){
                if (cnt[all[k].b] == q+i+1 || edges[all[k].b].w < all[ans[j]].w){
                    cnt[all[k].b] = i+1;
                    continue;
                }
             //   cout << all[k].b << " ";
                group(edges[all[k].b].a,edges[all[k].b].b);
            }
          // cout << '\n';
            int c = all[ans[j]].b;
            c = gp(c);
            res[ans[j]] = ssize[c];
            reset(osize);
        }
        reset(0);
        for (int j : cvis) edges[all[j].b].w = all[j].w;
    }
    
    for (int i =0; i < q; i++){
        if (all[i].a == 1) continue;
        cout << res[i] << "\n";
        if (res[i] == -1) while (true) continue;
    }
 
    return 0;
}

Compilation message

bridges.cpp: In function 'void reset(int)':
bridges.cpp:49:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |     while (upd.sz() > a){
      |            ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (int j = 0; j < ans.sz(); j++){
      |                         ~~^~~~~~~~~~
bridges.cpp:119:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             while (cidx < curre.sz() && edges[curre[cidx]].w >= all[ans[j]].w){
      |                    ~~~~~^~~~~~~~~~~~
bridges.cpp:115:13: warning: unused variable 'u' [-Wunused-variable]
  115 |         int u,v;
      |             ^
bridges.cpp:115:15: warning: unused variable 'v' [-Wunused-variable]
  115 |         int u,v;
      |               ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 14 ms 2708 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 6 ms 2904 KB Output is correct
7 Correct 7 ms 2652 KB Output is correct
8 Correct 8 ms 2704 KB Output is correct
9 Correct 7 ms 2648 KB Output is correct
10 Correct 9 ms 2652 KB Output is correct
11 Correct 8 ms 2652 KB Output is correct
12 Correct 8 ms 2652 KB Output is correct
13 Correct 9 ms 2832 KB Output is correct
14 Correct 8 ms 2884 KB Output is correct
15 Correct 9 ms 2648 KB Output is correct
16 Correct 8 ms 2904 KB Output is correct
17 Correct 7 ms 2652 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2302 ms 4424 KB Output is correct
2 Correct 2363 ms 4184 KB Output is correct
3 Correct 2379 ms 4184 KB Output is correct
4 Correct 2291 ms 4180 KB Output is correct
5 Correct 2320 ms 4180 KB Output is correct
6 Correct 2496 ms 4564 KB Output is correct
7 Correct 2501 ms 4432 KB Output is correct
8 Correct 2506 ms 4436 KB Output is correct
9 Correct 41 ms 3160 KB Output is correct
10 Correct 1028 ms 4304 KB Output is correct
11 Correct 1103 ms 4188 KB Output is correct
12 Correct 2359 ms 4560 KB Output is correct
13 Correct 2338 ms 4180 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1459 ms 3840 KB Output is correct
2 Correct 421 ms 3412 KB Output is correct
3 Correct 1454 ms 4088 KB Output is correct
4 Correct 1463 ms 3852 KB Output is correct
5 Correct 41 ms 3160 KB Output is correct
6 Correct 1453 ms 3836 KB Output is correct
7 Correct 1451 ms 3832 KB Output is correct
8 Correct 1405 ms 3832 KB Output is correct
9 Correct 1367 ms 4084 KB Output is correct
10 Correct 1362 ms 4088 KB Output is correct
11 Correct 1399 ms 3920 KB Output is correct
12 Correct 1331 ms 3832 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 4880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2302 ms 4424 KB Output is correct
2 Correct 2363 ms 4184 KB Output is correct
3 Correct 2379 ms 4184 KB Output is correct
4 Correct 2291 ms 4180 KB Output is correct
5 Correct 2320 ms 4180 KB Output is correct
6 Correct 2496 ms 4564 KB Output is correct
7 Correct 2501 ms 4432 KB Output is correct
8 Correct 2506 ms 4436 KB Output is correct
9 Correct 41 ms 3160 KB Output is correct
10 Correct 1028 ms 4304 KB Output is correct
11 Correct 1103 ms 4188 KB Output is correct
12 Correct 2359 ms 4560 KB Output is correct
13 Correct 2338 ms 4180 KB Output is correct
14 Correct 1459 ms 3840 KB Output is correct
15 Correct 421 ms 3412 KB Output is correct
16 Correct 1454 ms 4088 KB Output is correct
17 Correct 1463 ms 3852 KB Output is correct
18 Correct 41 ms 3160 KB Output is correct
19 Correct 1453 ms 3836 KB Output is correct
20 Correct 1451 ms 3832 KB Output is correct
21 Correct 1405 ms 3832 KB Output is correct
22 Correct 1367 ms 4084 KB Output is correct
23 Correct 1362 ms 4088 KB Output is correct
24 Correct 1399 ms 3920 KB Output is correct
25 Correct 1331 ms 3832 KB Output is correct
26 Correct 2318 ms 4184 KB Output is correct
27 Correct 2437 ms 4300 KB Output is correct
28 Correct 2413 ms 4308 KB Output is correct
29 Correct 2291 ms 4180 KB Output is correct
30 Correct 2427 ms 4308 KB Output is correct
31 Correct 2468 ms 4416 KB Output is correct
32 Correct 2452 ms 4184 KB Output is correct
33 Correct 2371 ms 4184 KB Output is correct
34 Correct 2389 ms 4180 KB Output is correct
35 Correct 2403 ms 4180 KB Output is correct
36 Correct 2350 ms 4188 KB Output is correct
37 Correct 2327 ms 4428 KB Output is correct
38 Correct 2317 ms 4304 KB Output is correct
39 Correct 2292 ms 4180 KB Output is correct
40 Correct 2312 ms 4180 KB Output is correct
41 Correct 2235 ms 4184 KB Output is correct
42 Correct 2149 ms 4180 KB Output is correct
43 Correct 2166 ms 4308 KB Output is correct
44 Correct 2192 ms 4176 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 14 ms 2708 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 6 ms 2904 KB Output is correct
7 Correct 7 ms 2652 KB Output is correct
8 Correct 8 ms 2704 KB Output is correct
9 Correct 7 ms 2648 KB Output is correct
10 Correct 9 ms 2652 KB Output is correct
11 Correct 8 ms 2652 KB Output is correct
12 Correct 8 ms 2652 KB Output is correct
13 Correct 9 ms 2832 KB Output is correct
14 Correct 8 ms 2884 KB Output is correct
15 Correct 9 ms 2648 KB Output is correct
16 Correct 8 ms 2904 KB Output is correct
17 Correct 7 ms 2652 KB Output is correct
18 Correct 2302 ms 4424 KB Output is correct
19 Correct 2363 ms 4184 KB Output is correct
20 Correct 2379 ms 4184 KB Output is correct
21 Correct 2291 ms 4180 KB Output is correct
22 Correct 2320 ms 4180 KB Output is correct
23 Correct 2496 ms 4564 KB Output is correct
24 Correct 2501 ms 4432 KB Output is correct
25 Correct 2506 ms 4436 KB Output is correct
26 Correct 41 ms 3160 KB Output is correct
27 Correct 1028 ms 4304 KB Output is correct
28 Correct 1103 ms 4188 KB Output is correct
29 Correct 2359 ms 4560 KB Output is correct
30 Correct 2338 ms 4180 KB Output is correct
31 Correct 1459 ms 3840 KB Output is correct
32 Correct 421 ms 3412 KB Output is correct
33 Correct 1454 ms 4088 KB Output is correct
34 Correct 1463 ms 3852 KB Output is correct
35 Correct 41 ms 3160 KB Output is correct
36 Correct 1453 ms 3836 KB Output is correct
37 Correct 1451 ms 3832 KB Output is correct
38 Correct 1405 ms 3832 KB Output is correct
39 Correct 1367 ms 4084 KB Output is correct
40 Correct 1362 ms 4088 KB Output is correct
41 Correct 1399 ms 3920 KB Output is correct
42 Correct 1331 ms 3832 KB Output is correct
43 Execution timed out 3085 ms 4880 KB Time limit exceeded
44 Halted 0 ms 0 KB -