oj.uz

Submission #690533

# Submission time Handle Problem Language Result Execution time Memory
690533 2023-01-30T09:16:13 Z thinh1711 Bridges (APIO19_bridges) C++17
13 / 100
 3000 ms 7428 KB 
#include <bits/stdc++.h>
#define reu(i,a,b) for (int i=a;i<=b;++i)
#define pb push_back
using namespace std;
int n,m;
const int mx=100002;
int bridge[mx];
vector<pair<int , int> > ke[mx];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    reu(i,1,m){
       int u,v,d;
       cin>>u>>v;
       ke[u].pb({v,i});
       ke[v].pb({u,i});
       cin>>d;
       bridge[i]=d;
     }
    int q;
    cin>>q;
    reu(i,1,q)
    {
        int typ;
        cin>>typ;
        if (typ==1){
            int v,w;
            cin>>v>>w;
            bridge[v]=w;
        }
        else {
            bool is[mx];
            int cnt=1;
            memset(is,true,sizeof(is));
            int w,s;
            cin>>s>>w;
            is[s]=false;
            queue<int> q;
            q.push(s);
            while (!q.empty()){
                int h=q.front();
                q.pop();
                for (auto x:ke[h])
                              if (is[x.first]==true) if (bridge[x.second]>=w){
                                    is[x.first]=false;
                                    q.push(x.first);
                                    ++cnt;
                                }
            }
            cout<<cnt<<"\n";
        }
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 44 ms 2824 KB Output is correct
4 Correct 26 ms 2772 KB Output is correct
5 Correct 18 ms 2780 KB Output is correct
6 Correct 17 ms 2772 KB Output is correct
7 Correct 22 ms 2900 KB Output is correct
8 Correct 19 ms 2772 KB Output is correct
9 Correct 19 ms 2788 KB Output is correct
10 Correct 19 ms 2784 KB Output is correct
11 Correct 16 ms 2792 KB Output is correct
12 Correct 16 ms 2772 KB Output is correct
13 Correct 21 ms 2792 KB Output is correct
14 Correct 18 ms 2784 KB Output is correct
15 Correct 19 ms 2776 KB Output is correct
16 Correct 19 ms 2780 KB Output is correct
17 Correct 20 ms 2792 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 6112 KB Output is correct
2 Correct 171 ms 7336 KB Output is correct
3 Correct 175 ms 7428 KB Output is correct
4 Correct 295 ms 7420 KB Output is correct
5 Correct 297 ms 7372 KB Output is correct
6 Execution timed out 3090 ms 6048 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 5836 KB Output is correct
2 Correct 2334 ms 4860 KB Output is correct
3 Execution timed out 3055 ms 5668 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 6112 KB Output is correct
2 Correct 171 ms 7336 KB Output is correct
3 Correct 175 ms 7428 KB Output is correct
4 Correct 295 ms 7420 KB Output is correct
5 Correct 297 ms 7372 KB Output is correct
6 Execution timed out 3090 ms 6048 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 44 ms 2824 KB Output is correct
4 Correct 26 ms 2772 KB Output is correct
5 Correct 18 ms 2780 KB Output is correct
6 Correct 17 ms 2772 KB Output is correct
7 Correct 22 ms 2900 KB Output is correct
8 Correct 19 ms 2772 KB Output is correct
9 Correct 19 ms 2788 KB Output is correct
10 Correct 19 ms 2784 KB Output is correct
11 Correct 16 ms 2792 KB Output is correct
12 Correct 16 ms 2772 KB Output is correct
13 Correct 21 ms 2792 KB Output is correct
14 Correct 18 ms 2784 KB Output is correct
15 Correct 19 ms 2776 KB Output is correct
16 Correct 19 ms 2780 KB Output is correct
17 Correct 20 ms 2792 KB Output is correct
18 Correct 171 ms 6112 KB Output is correct
19 Correct 171 ms 7336 KB Output is correct
20 Correct 175 ms 7428 KB Output is correct
21 Correct 295 ms 7420 KB Output is correct
22 Correct 297 ms 7372 KB Output is correct
23 Execution timed out 3090 ms 6048 KB Time limit exceeded
24 Halted 0 ms 0 KB -