oj.uz

Submission #962533

# Submission time Handle Problem Language Result Execution time Memory
962533 2024-04-13T18:44:52 Z Amr Bridges (APIO19_bridges) C++17
14 / 100
 176 ms 15712 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=1e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x; // % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)  ; // % mod;
        y = y>>1;
        x = (x*x) ; // % mod;
    }
    return res;
}

ll n , m;
vector<ll> e[N];
ll p[N];
ll siz[N];
ll ans[N];
pair<ll,ll> qu[N];
vector<pair<ll,ll> > vec;
ll get(ll x)
{
    if(x==p[x]) return x;
    return p[x] = get(p[x]);
}
void merg(ll x, ll y){
    x = get(x);
    y = get(y);
    if(x==y) return;
    p[x] = y;
    siz[y] +=siz[x];
}
void solve()
{
    ll n , m; cin >> n >> m;
    for(int i =1; i <= n; i++) p[i] = i, siz[i] = 1;
    for(int i = 0; i < m; i++)
    {
        e[i].resize(3);
        cin >> e[i][1] >> e[i][2] >> e[i][0];
    }
    sort(e,e+m); reverse(e,e+m);
    ll q; cin >> q;
    for(int i = 0; i < q; i++)
    {
        ll tp ; cin >> tp;
        cin >> qu[i].F >> qu[i].S;
        vec.push_back({qu[i].S,i});
    }
    sort(all(vec)); reverse(all(vec));
    ll l = 0, r = 0;
    while(l<q||r<m)
    {
        if(r==m||(l<q&&e[r][0]<vec[l].F))
        {
            ans[vec[l].S] = siz[get(qu[vec[l].S].F)];
            l++;
        }
        else
        {
            ll x = e[r][1] , y = e[r][2];
            merg(x,y);
            r++;
        }
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << " "; cout << endl;
}
int main(){
    //freopen("friday.in","r",stdin);
    //freopen("frid
    while(TT--)
        solve();

    return 0;
}

Compilation message

bridges.cpp: In function 'void solve()':
bridges.cpp:83:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   83 |     for(int i = 0; i < q; i++)
      |     ^~~
bridges.cpp:84:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   84 |         cout << ans[i] << " "; cout << endl;
      |                                ^~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 10244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 9760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 12000 KB Output is correct
2 Correct 64 ms 9416 KB Output is correct
3 Correct 102 ms 11788 KB Output is correct
4 Correct 92 ms 11924 KB Output is correct
5 Correct 125 ms 14284 KB Output is correct
6 Correct 161 ms 15632 KB Output is correct
7 Correct 138 ms 14284 KB Output is correct
8 Correct 112 ms 12740 KB Output is correct
9 Correct 125 ms 12744 KB Output is correct
10 Correct 116 ms 12620 KB Output is correct
11 Correct 137 ms 14044 KB Output is correct
12 Correct 137 ms 14280 KB Output is correct
13 Correct 137 ms 14044 KB Output is correct
14 Correct 141 ms 14280 KB Output is correct
15 Correct 128 ms 14300 KB Output is correct
16 Correct 156 ms 15440 KB Output is correct
17 Correct 163 ms 15512 KB Output is correct
18 Correct 161 ms 15544 KB Output is correct
19 Correct 176 ms 15712 KB Output is correct
20 Correct 137 ms 14660 KB Output is correct
21 Correct 136 ms 14472 KB Output is correct
22 Correct 159 ms 15480 KB Output is correct
23 Correct 112 ms 13440 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 10244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -