oj.uz

Submission #130233

# Submission time Handle Problem Language Result Execution time Memory
130233 2019-07-14T10:54:38 Z combi1k1 Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 13208 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
const int   N   = 1e5 + 5;
const int   B   = 500;
 
#define pb      push_back
#define all(x)  x.begin(),x.end()
#define sz(x)   x.size()
#define X       first
#define Y       second
 
typedef pair<int,int>   ii;
typedef pair<int,ii>    pii;
typedef vector<pii>     vi;
 
struct Edge {
	int x, y;
	int w, i;
	bool operator < (const Edge &a) const   {
        return  ii(w,i) > ii(a.w,a.i);
	}
};
struct Ques {
    int mas, ver, idx;
    bool operator < (const Ques& a) const   {
        return  mas > a.mas;
    }
};
 
bool uV[N], uE[N];
 
namespace DSU   {
    int p[N], s[N];
    int lead(int x) {
        return  p[x] == x ? x : p[x] = lead(p[x]);
    }
    int join(int x,int y)   {
        x = lead(x);
        y = lead(y);
        if (x == y) return  0;
        if (uV[y])  swap(x,y);
        p[y] = x;
        s[x] += s[y];
        return  1;
    }
};
 
set<Edge>   E;
int n, m;
int x[N], y[N], w[N];
 
void calc(vector<Ques>  qr) {
    iota(DSU::p + 1,DSU::p + 1 + n,1);
    fill(DSU::s + 1,DSU::s + 1 + n,1);
    fill(uV + 1,uV + 1 + n,0);
    fill(uE + 1,uE + 1 + m,0);
    vector<Ques>    sta;
    vector<int>     vx;
    vector<int>     ed;
    map<int,vi> mp;
    for(Ques t : qr)    {
        if(!t.idx)  uE[t.ver] = 1,  uV[x[t.ver]] = uV[y[t.ver]] = 1;
        else        sta.pb(t),      uV[t.ver] = 1;
    }
    for(int i = 1 ; i <= n ; ++i)   if (uV[i])  vx.pb(i);
    for(int i = 1 ; i <= m ; ++i)   if (uE[i])  ed.pb(i);
    sort(all(sta));
    auto it = E.begin();
    for(Ques t : sta)   {
        while (it != E.end() && (*it).w >= t.mas)   {
            if(!uE[(*it).i])    DSU::join((*it).x,(*it).y);
            it++;
        }
        for(int x : vx) mp[t.idx].pb(pii(x,{DSU::lead(x),DSU::s[DSU::p[x]]}));
    }
    for(Ques q : qr)    {
        if(!q.idx)  {
            Edge it = *E.find({x[q.ver],y[q.ver],w[q.ver],q.ver});
            E.erase(it);    it.w = w[q.ver] = q.mas;
            E.insert(it);   continue;
        }
        for(pii t : mp[q.idx])  DSU::p[t.X] = t.Y.X, DSU::s[t.X] = t.Y.Y;
        for(int i : ed) if (w[i] >= q.mas)
            DSU::join(x[i],y[i]);
        cout << DSU::s[DSU::lead(q.ver)] << "\n";
    }
}
 
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
 
    for(int i = 1 ; i <= m ; ++i)    {
        cin >> x[i] >> y[i] >> w[i];
        E.insert({x[i],y[i],w[i],i});
    }
 
    int q;  cin >> q;
 
    vector<Ques>    v;
 
    for(int i = 1 ; i <= q ; ++i)   {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) v.pb({y,x,0});
        if (t == 2) v.pb({y,x,i});
    }
 
    for(int i = 0 ; i < q ; i += B)
        calc(vector<Ques>(v.begin() + i,v.begin() + min((int)v.size(),i + B)));
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 42 ms 1220 KB Output is correct
4 Correct 9 ms 792 KB Output is correct
5 Correct 19 ms 820 KB Output is correct
6 Correct 16 ms 820 KB Output is correct
7 Correct 33 ms 1088 KB Output is correct
8 Correct 35 ms 1108 KB Output is correct
9 Correct 37 ms 1048 KB Output is correct
10 Correct 34 ms 1092 KB Output is correct
11 Correct 33 ms 1132 KB Output is correct
12 Correct 35 ms 1108 KB Output is correct
13 Correct 40 ms 1132 KB Output is correct
14 Correct 38 ms 1224 KB Output is correct
15 Correct 40 ms 1172 KB Output is correct
16 Correct 34 ms 1028 KB Output is correct
17 Correct 34 ms 1092 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2961 ms 11280 KB Output is correct
2 Correct 2820 ms 12072 KB Output is correct
3 Correct 2849 ms 12012 KB Output is correct
4 Correct 2859 ms 11908 KB Output is correct
5 Correct 2875 ms 11988 KB Output is correct
6 Execution timed out 3043 ms 11572 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2677 ms 8080 KB Output is correct
2 Correct 1908 ms 7592 KB Output is correct
3 Correct 2878 ms 9692 KB Output is correct
4 Correct 2674 ms 9592 KB Output is correct
5 Correct 74 ms 3308 KB Output is correct
6 Correct 2822 ms 9704 KB Output is correct
7 Correct 2715 ms 9644 KB Output is correct
8 Correct 2528 ms 9596 KB Output is correct
9 Execution timed out 3041 ms 10704 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2961 ms 11280 KB Output is correct
2 Correct 2820 ms 12072 KB Output is correct
3 Correct 2849 ms 12012 KB Output is correct
4 Correct 2859 ms 11908 KB Output is correct
5 Correct 2875 ms 11988 KB Output is correct
6 Execution timed out 3043 ms 11572 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 42 ms 1220 KB Output is correct
4 Correct 9 ms 792 KB Output is correct
5 Correct 19 ms 820 KB Output is correct
6 Correct 16 ms 820 KB Output is correct
7 Correct 33 ms 1088 KB Output is correct
8 Correct 35 ms 1108 KB Output is correct
9 Correct 37 ms 1048 KB Output is correct
10 Correct 34 ms 1092 KB Output is correct
11 Correct 33 ms 1132 KB Output is correct
12 Correct 35 ms 1108 KB Output is correct
13 Correct 40 ms 1132 KB Output is correct
14 Correct 38 ms 1224 KB Output is correct
15 Correct 40 ms 1172 KB Output is correct
16 Correct 34 ms 1028 KB Output is correct
17 Correct 34 ms 1092 KB Output is correct
18 Correct 2961 ms 11280 KB Output is correct
19 Correct 2820 ms 12072 KB Output is correct
20 Correct 2849 ms 12012 KB Output is correct
21 Correct 2859 ms 11908 KB Output is correct
22 Correct 2875 ms 11988 KB Output is correct
23 Execution timed out 3043 ms 11572 KB Time limit exceeded
24 Halted 0 ms 0 KB -