oj.uz

Submission #690526

# Submission time Handle Problem Language Result Execution time Memory
690526 2023-01-30T09:13:17 Z thinh1711 Bridges (APIO19_bridges) C++17
13 / 100
 43 ms 4180 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];
int dist[100002];
vector<pair<int , int> > ke[10002];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(dist,0,sizeof(dist));
    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 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 43 ms 1080 KB Output is correct
4 Correct 25 ms 980 KB Output is correct
5 Correct 17 ms 1056 KB Output is correct
6 Correct 22 ms 1048 KB Output is correct
7 Correct 23 ms 1052 KB Output is correct
8 Correct 26 ms 1044 KB Output is correct
9 Correct 20 ms 1060 KB Output is correct
10 Correct 15 ms 980 KB Output is correct
11 Correct 15 ms 1064 KB Output is correct
12 Correct 16 ms 980 KB Output is correct
13 Correct 18 ms 1048 KB Output is correct
14 Correct 18 ms 980 KB Output is correct
15 Correct 19 ms 1056 KB Output is correct
16 Correct 19 ms 1056 KB Output is correct
17 Correct 20 ms 1052 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 3712 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 4180 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 3712 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 43 ms 1080 KB Output is correct
4 Correct 25 ms 980 KB Output is correct
5 Correct 17 ms 1056 KB Output is correct
6 Correct 22 ms 1048 KB Output is correct
7 Correct 23 ms 1052 KB Output is correct
8 Correct 26 ms 1044 KB Output is correct
9 Correct 20 ms 1060 KB Output is correct
10 Correct 15 ms 980 KB Output is correct
11 Correct 15 ms 1064 KB Output is correct
12 Correct 16 ms 980 KB Output is correct
13 Correct 18 ms 1048 KB Output is correct
14 Correct 18 ms 980 KB Output is correct
15 Correct 19 ms 1056 KB Output is correct
16 Correct 19 ms 1056 KB Output is correct
17 Correct 20 ms 1052 KB Output is correct
18 Runtime error 12 ms 3712 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -