oj.uz

Submission #962535

# Submission time Handle Problem Language Result Execution time Memory
962535 2024-04-13T18:48:42 Z Amr Bridges (APIO19_bridges) C++17
14 / 100
 180 ms 12148 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;
    while(l<q&&(m==0||e[0][0]<vec[l].F))
    {
        ans[vec[l].S] = 1;
        l++;
    }
    for(int i = 0; i < m; i++)
    {
        ll x = e[i][1] , y = e[i][2];
        merg(x,y);
        while(l<q&&(i==m-1||e[i+1][0]<vec[l].F))
        {
            //cout << i << endl;
            ans[vec[l].S] = siz[get(qu[vec[l].S].F)];
            l++;
        }
    }
    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:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |     for(int i = 0; i < q; i++)
      |     ^~~
bridges.cpp:86:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   86 |         cout << ans[i] << " "; cout << endl;
      |                                ^~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 118 ms 10208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 9680 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 180 ms 11856 KB Output is correct
2 Correct 60 ms 8648 KB Output is correct
3 Correct 93 ms 10020 KB Output is correct
4 Correct 93 ms 9940 KB Output is correct
5 Correct 140 ms 11980 KB Output is correct
6 Correct 168 ms 11984 KB Output is correct
7 Correct 125 ms 11980 KB Output is correct
8 Correct 109 ms 10188 KB Output is correct
9 Correct 114 ms 10412 KB Output is correct
10 Correct 116 ms 10184 KB Output is correct
11 Correct 129 ms 11212 KB Output is correct
12 Correct 136 ms 11212 KB Output is correct
13 Correct 133 ms 11208 KB Output is correct
14 Correct 121 ms 11920 KB Output is correct
15 Correct 128 ms 11984 KB Output is correct
16 Correct 157 ms 11836 KB Output is correct
17 Correct 159 ms 12148 KB Output is correct
18 Correct 155 ms 11912 KB Output is correct
19 Correct 166 ms 11764 KB Output is correct
20 Correct 133 ms 11524 KB Output is correct
21 Correct 132 ms 11336 KB Output is correct
22 Correct 148 ms 11720 KB Output is correct
23 Correct 115 ms 11464 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

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