oj.uz

Submission #724662

# Submission time Handle Problem Language Result Execution time Memory
724662 2023-04-15T17:22:04 Z n0sk1ll Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 9236 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

set<pair<int,pii>> prim;
pair<int,pii> ed[100003];

pair<int,pii> qry[100003];

int up[50003];
int Up(int x)
{
    if (up[x]<0) return x;
    return up[x]=Up(up[x]);
}

void dsu(int a, int b)
{
    a=Up(a),b=Up(b); if (a==b) return;
    if (up[a]<up[b]) swap(a,b);
    up[b]+=up[a],up[a]=b;
}

void rebuild(int n)
{
    fff(i,1,n) up[i]=-1;
}

void solvebrut(int n, int m, int q)
{
    fff(i,1,q)
    {
        if (qry[i].xx==1)
        {
            ed[qry[i].yy.xx].xx=qry[i].yy.yy;
        }
        else
        {
            rebuild(n);
            fff(j,1,m) if (ed[j].xx>=qry[i].yy.yy) dsu(ed[j].yy.xx,ed[j].yy.yy);
            cout<<-up[Up(qry[i].yy.xx)]<<"\n";
        }
    }
}

int main()
{
    FAST;

    int n,m; cin>>n>>m;
    fff(i,1,m)
    {
        cin>>ed[i].yy.xx>>ed[i].yy.yy>>ed[i].xx;
        prim.insert(ed[i]);
    }

    int q; cin>>q;
    fff(i,1,q) cin>>qry[i].xx>>qry[i].yy.xx>>qry[i].yy.yy;

    if (n<=1000 && m<=1000 && q<=10000) solvebrut(n,m,q);
    else solvebrut(n,m,q);
}

//Note to self: Check for overflow

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 32 ms 612 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 6 ms 436 KB Output is correct
8 Correct 8 ms 596 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 6 ms 592 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 9 ms 612 KB Output is correct
14 Correct 8 ms 612 KB Output is correct
15 Correct 10 ms 588 KB Output is correct
16 Correct 6 ms 468 KB Output is correct
17 Correct 6 ms 468 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 32 ms 612 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 6 ms 436 KB Output is correct
8 Correct 8 ms 596 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 6 ms 592 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 9 ms 612 KB Output is correct
14 Correct 8 ms 612 KB Output is correct
15 Correct 10 ms 588 KB Output is correct
16 Correct 6 ms 468 KB Output is correct
17 Correct 6 ms 468 KB Output is correct
18 Execution timed out 3055 ms 5528 KB Time limit exceeded
19 Halted 0 ms 0 KB -