oj.uz

Submission #263933

# Submission time Handle Problem Language Result Execution time Memory
263933 2020-08-14T04:20:33 Z jeqcho Bridges (APIO19_bridges) C++17
44 / 100
 3000 ms 10088 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef int us;
typedef long long ll;
typedef pair<us,us> ii;
typedef vector<int> vi;

int C = 650;

ii L[1000001];
int par[51111];
int curcnt=0;

void init()
{
    memset(par,-1,sizeof(par));
    curcnt=0;
}

us rt(us u, us ty=0)
{
    if(par[u]<0) return u;
    else
    {
        if(ty) return (par[u]=rt(par[u]));
        else return rt(par[u]);
    }
}

void merge(us u, us v, us ty=0)
{
    u=rt(u,ty); v=rt(v,ty);
    if(u==v) return ;
   // if(par[u]==par[v]&&(rand()%2==0)) swap(u,v);
    if(par[u]>par[v]) swap(u,v);
    // par[u] must be negative, and enforcing par[u] <= par[v] ensures par[u] has bigger size
    L[curcnt++] = {v,-par[v]};
    par[u]+=par[v];
    // par[v] is now positive, and this value is used for rollback and traversing
    // par[] stores size of component for representative, stores parent for non-representative
    // if par[i] < 0, i is a representative with component size of -par[i]
    par[v]=u;
}

void rollback()
{
	int cc=curcnt-1;
    int u=par[L[cc].fi];
    par[u]+=L[cc].se;
    par[L[cc].fi]=-L[cc].se;
    curcnt--;
}

ii E[121311];
int W[121311];
int ans[121311];
pair<int,pair<int,int> > queries[123231];
vector<pair<int,pair<ii,ii> > > edges;
int n,m;

void update(int l, int r)
{
    for(int i=l;i<=r;i++)
    {
        if(queries[i].fi==1)
        {
            int lab=queries[i].se.fi; int w=queries[i].se.se;
            W[lab]=w;
        }
    }
}

void solve(int l, int r)
{
    // vector<pair<update time or id,pair<bridge id,new weight> > > UD;
    vector<pair<int,pair<int,int> > > UD;
    // vector<id of bridge in order of updates>
    vi bad;
    for(int i=l;i<=r;i++) // O(sqrt(q))
    {
        if(queries[i].fi==1)
        {
            // lab is bridge id
            int lab=queries[i].se.fi; int w=queries[i].se.se;
            bad.pb(lab);
            UD.pb({i,{lab,w}});
        }
    }
    vector<pair<int,pair<int,int> > > Q;
    for(int i=l;i<=r;i++) // O(sqrt(q))
    {
        if(queries[i].fi==2)
        {
            int u=queries[i].se.fi; int w=queries[i].se.se;
            Q.pb({w,{u,i}});
        }
    }
    sort(Q.rbegin(),Q.rend());  // O(sqrt(q log q))
    int ptr=0;
    // start new DSU structure
    init(); // O(n)
    for(int i=0;i<Q.size();i++)// O(sqrt(q))
    {
        // process query from heaviest car
        int w=Q[i].fi; int u=Q[i].se.fi; int lab=Q[i].se.se;
        // for all bridges with ok previous weight limit
        while(ptr<edges.size()&&edges[ptr].fi>=w) // O(q+m) directly to solve(), not nested in upper for loop
        {
            // if time of last update is less than l and time of the described update is greater than r
            // i.e. this update doesn't occur during time bucket
            // i.e. no update of this bridge occurs during time bucket
            // updates before have already been committed
            // updates after time bucket is of no concern
            if(edges[ptr].se.se.fi<=l&&edges[ptr].se.se.se>=r)
                // merge the nodes mentioned in edges[ptr] with path compression
                // these will not be rolled back
                merge(edges[ptr].se.fi.fi,edges[ptr].se.fi.se,1); // O(log n)
            ptr++;
        }
        vector<pair<int,int> > upd;
        int pt=0;
        // for all updates in time bucket happening before the query
        while(pt<UD.size()&&UD[pt].fi<=lab) // O(sqrt(q))
        {
            int lab=UD[pt].se.fi; int w=UD[pt].se.se;
            // store state before modification
            // these states will be reverted since queries are processed offline
            upd.pb({lab,W[lab]});
            W[lab]=w;
            pt++;
        }
        // mark current version id, will rollback to this state
        int curl=curcnt;
        // for all updates in time bucket
        // x is bridge id
        for(int x:bad) // O(sqrt(q))
        {
            int u=E[x].fi; int v=E[x].se; int ww=W[x];
            // w is car weight
            // if the updated bridge limit is ok for car
            if(w<=ww)
            {
                // these merges will be rolled back (no path compression)
                merge(u,v);
            }
        }
        ans[lab]=-par[rt(u)];
        while(curcnt>curl) rollback(); // O(sqrt(q))
        reverse(upd.begin(),upd.end()); // O(sqrt(q))
        for(auto t:upd) W[t.fi]=t.se; // O(sqrt(q))
    }
    // commit all updates in time bucket
    update(l,r);    // O(sqrt(q))
}

int las[111111];
int preW[111111];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    memset(ans,-1,sizeof(ans));
    for(int i=0;i<m;i++)
    {
        int u,v,w; cin>>u>>v>>w; u--; v--;
        E[i]=mp(u,v); W[i]=preW[i]=w;
    }
    int q; cin>>q;
    int q1=0;
    for(int i=0;i<q;i++) // O(q)
    {
        int a,b,c; cin>>a>>b>>c; b--;
        if(a==1)
        {
			if(las[b]<=i-1) edges.pb({preW[b],{{E[b].fi,E[b].se},{las[b],i-1}}});
			las[b]=i; preW[b]=c;
		}
        queries[i]={a,{b,c}};
    }
    for(int i=0;i<m;i++) // O(m)
    {
		if(las[i]<=q-1)
		{
			edges.pb({preW[i],{{E[i].fi,E[i].se},{las[i],q-1}}});
		}
	}
	sort(edges.rbegin(),edges.rend()); // O( (m+q) log (m+q) )
    int l=0; int r=0;
    // O(q) loop
    // calls solve for O(sqrt(q)) times
    while(r<q)
    {
        if(queries[r].fi==1) q1++;
        // C is sqrt(n)
        if(q1>=C)
        {
            solve(l,r);
            l=r+1;
            q1=0;
        }
        r++;
    }
    if(l<q) solve(l,q-1);
    for(int i=0;i<q;i++)
    {
        if(ans[i]!=-1) cout<<ans[i]<<'\n';
    }
}

Compilation message

bridges.cpp: In function 'void solve(int, int)':
bridges.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i=0;i<Q.size();i++)// O(sqrt(q))
      |                 ~^~~~~~~~~
bridges.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::pair<int, int>, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         while(ptr<edges.size()&&edges[ptr].fi>=w) // O(q+m) directly to solve(), not nested in upper for loop
      |               ~~~^~~~~~~~~~~~~
bridges.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         while(pt<UD.size()&&UD[pt].fi<=lab) // O(sqrt(q))
      |               ~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 45 ms 1632 KB Output is correct
4 Correct 5 ms 1600 KB Output is correct
5 Correct 64 ms 1504 KB Output is correct
6 Correct 50 ms 1624 KB Output is correct
7 Correct 61 ms 1548 KB Output is correct
8 Correct 59 ms 1620 KB Output is correct
9 Correct 56 ms 1504 KB Output is correct
10 Correct 66 ms 1604 KB Output is correct
11 Correct 59 ms 1528 KB Output is correct
12 Correct 73 ms 1624 KB Output is correct
13 Correct 70 ms 1608 KB Output is correct
14 Correct 63 ms 1624 KB Output is correct
15 Correct 76 ms 1624 KB Output is correct
16 Correct 62 ms 1536 KB Output is correct
17 Correct 61 ms 1504 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 7016 KB Output is correct
2 Correct 1138 ms 6936 KB Output is correct
3 Correct 1141 ms 6928 KB Output is correct
4 Correct 1217 ms 6928 KB Output is correct
5 Correct 1179 ms 6928 KB Output is correct
6 Correct 1893 ms 7192 KB Output is correct
7 Correct 1889 ms 7192 KB Output is correct
8 Correct 1822 ms 7268 KB Output is correct
9 Correct 57 ms 4976 KB Output is correct
10 Correct 1293 ms 7080 KB Output is correct
11 Correct 1163 ms 7004 KB Output is correct
12 Execution timed out 3081 ms 6124 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 990 ms 6512 KB Output is correct
2 Correct 1006 ms 5116 KB Output is correct
3 Correct 1508 ms 6512 KB Output is correct
4 Correct 1076 ms 6524 KB Output is correct
5 Correct 45 ms 4848 KB Output is correct
6 Correct 1261 ms 6508 KB Output is correct
7 Correct 907 ms 6548 KB Output is correct
8 Correct 787 ms 6668 KB Output is correct
9 Correct 1691 ms 5668 KB Output is correct
10 Correct 1314 ms 5648 KB Output is correct
11 Correct 586 ms 6912 KB Output is correct
12 Correct 496 ms 6912 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 10088 KB Output is correct
2 Correct 46 ms 4856 KB Output is correct
3 Correct 50 ms 6380 KB Output is correct
4 Correct 78 ms 6380 KB Output is correct
5 Correct 98 ms 10080 KB Output is correct
6 Correct 119 ms 10088 KB Output is correct
7 Correct 94 ms 10088 KB Output is correct
8 Correct 76 ms 7528 KB Output is correct
9 Correct 76 ms 7528 KB Output is correct
10 Correct 78 ms 7660 KB Output is correct
11 Correct 92 ms 9184 KB Output is correct
12 Correct 93 ms 9192 KB Output is correct
13 Correct 98 ms 9104 KB Output is correct
14 Correct 102 ms 10088 KB Output is correct
15 Correct 102 ms 10084 KB Output is correct
16 Correct 103 ms 10048 KB Output is correct
17 Correct 116 ms 10008 KB Output is correct
18 Correct 113 ms 9956 KB Output is correct
19 Correct 106 ms 9992 KB Output is correct
20 Correct 94 ms 9440 KB Output is correct
21 Correct 91 ms 9444 KB Output is correct
22 Correct 124 ms 9828 KB Output is correct
23 Correct 86 ms 9320 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 7016 KB Output is correct
2 Correct 1138 ms 6936 KB Output is correct
3 Correct 1141 ms 6928 KB Output is correct
4 Correct 1217 ms 6928 KB Output is correct
5 Correct 1179 ms 6928 KB Output is correct
6 Correct 1893 ms 7192 KB Output is correct
7 Correct 1889 ms 7192 KB Output is correct
8 Correct 1822 ms 7268 KB Output is correct
9 Correct 57 ms 4976 KB Output is correct
10 Correct 1293 ms 7080 KB Output is correct
11 Correct 1163 ms 7004 KB Output is correct
12 Execution timed out 3081 ms 6124 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 45 ms 1632 KB Output is correct
4 Correct 5 ms 1600 KB Output is correct
5 Correct 64 ms 1504 KB Output is correct
6 Correct 50 ms 1624 KB Output is correct
7 Correct 61 ms 1548 KB Output is correct
8 Correct 59 ms 1620 KB Output is correct
9 Correct 56 ms 1504 KB Output is correct
10 Correct 66 ms 1604 KB Output is correct
11 Correct 59 ms 1528 KB Output is correct
12 Correct 73 ms 1624 KB Output is correct
13 Correct 70 ms 1608 KB Output is correct
14 Correct 63 ms 1624 KB Output is correct
15 Correct 76 ms 1624 KB Output is correct
16 Correct 62 ms 1536 KB Output is correct
17 Correct 61 ms 1504 KB Output is correct
18 Correct 1107 ms 7016 KB Output is correct
19 Correct 1138 ms 6936 KB Output is correct
20 Correct 1141 ms 6928 KB Output is correct
21 Correct 1217 ms 6928 KB Output is correct
22 Correct 1179 ms 6928 KB Output is correct
23 Correct 1893 ms 7192 KB Output is correct
24 Correct 1889 ms 7192 KB Output is correct
25 Correct 1822 ms 7268 KB Output is correct
26 Correct 57 ms 4976 KB Output is correct
27 Correct 1293 ms 7080 KB Output is correct
28 Correct 1163 ms 7004 KB Output is correct
29 Execution timed out 3081 ms 6124 KB Time limit exceeded
30 Halted 0 ms 0 KB -