oj.uz

Submission #972587

# Submission time Handle Problem Language Result Execution time Memory
972587 2024-04-30T16:34:48 Z simona1230 Bridges (APIO19_bridges) C++17
30 / 100
 3000 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

int n,m;
pair<int,int> e[100001];
int w[100001];
int q;
int t[100001],a[100001],b[100001];
void read()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        w[i]=c;
        e[i]={x,y};
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>t[i]>>a[i]>>b[i];
    }
}
const int block=315;

int used[100001];
vector<int> unch,qr,upd[100001];

bool cmp1(int x,int y)
{
    return w[x]>w[y];
}
bool cmp2(int x,int y)
{
    return b[x]>b[y];
}

struct rolling
{
    int x,szx,y,szy,rnkx,rnky;
    rolling(){}
    rolling(int _x,int _szx,int rx,int _y,int _szy,int ry)
    {
        x=_x;
        szx=_szx;
        y=_y;
        szy=_szy;

        rnkx=rx;
        rnky=ry;
    }
};
stack<rolling> s;
int ans[100001],rnk[100001],par[100001],sz[100001];

void init()
{
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        rnk[i]=0;
        par[i]=i;
    }
}

int find_parent(int x)
{
    if(x==par[x])return x;
    return find_parent(par[x]);
}

void unite(int idx)// idx is the index of the edge in e[]
{
    int i=e[idx].first;
    int j=e[idx].second;
    i=find_parent(i);
    j=find_parent(j);

    if(i!=j)
    {
        if(rnk[i]>rnk[j])
            swap(i,j);
        s.push({i,sz[i],rnk[i],j,sz[j],rnk[j]});
        par[i]=j;
        sz[j]+=sz[i];
        if(rnk[j]==rnk[i])
            rnk[j]++;
    }
}

void rollback(int prsz)
{
    while(s.size()!=prsz)
    {
        rolling r=s.top();
        s.pop();

        par[r.x]=r.x;
        sz[r.x]=r.szx;
        par[r.y]=r.y;
        sz[r.y]=r.szy;
    }
}

void solve()
{
    for(int l=1;l<=q;l+=block)
    {
        init();
        unch.clear();// the unchanged edges' indexes
        qr.clear();// the indexes of the queries in the original order
        int r=l+block-1;

        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
                used[a[i]]=l;
        }

        for(int i=1;i<=m;i++)
        {
            if(used[i]!=l)
                unch.push_back(i);
        }
        sort(unch.begin(),unch.end(),cmp1);

        for(int i=l;i<=r;i++)
        {
            if(t[i]==1)
                w[a[i]]=b[i];

            if(t[i]==2)
            {
                qr.push_back(i);
                for(int j=l;j<=r;j++)
                    if(t[j]==1&&w[a[j]]>=b[i])
                        upd[i].push_back(a[j]);
            }
        }
        // sort queries by weight of car big to small, then add edges >=
        // from the unchanged ones and the updates
        // afterwards rollback to before the updates and go on

        sort(qr.begin(),qr.end(),cmp2);

        int j=0;
        for(int i=0;i<qr.size();i++)
        {
            int lim=b[qr[i]];
            while(j<unch.size()&&w[unch[j]]>=lim)
            {
                unite(unch[j]);
                j++;
            }

            int prsz=s.size();
            for(int j=0;j<upd[qr[i]].size();j++)
                unite(upd[qr[i]][j]);

            ans[qr[i]]=sz[find_parent(a[qr[i]])];

            rollback(prsz);
        }
    }

    for(int i=1;i<=q;i++)
        if(t[i]==2)
            cout<<ans[i]<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	return 0;
}

Compilation message

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:95:19: warning: comparison of integer expressions of different signedness: 'std::stack<rolling>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     while(s.size()!=prsz)
      |           ~~~~~~~~^~~~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int i=0;i<qr.size();i++)
      |                     ~^~~~~~~~~~
bridges.cpp:152:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             while(j<unch.size()&&w[unch[j]]>=lim)
      |                   ~^~~~~~~~~~~~
bridges.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |             for(int j=0;j<upd[qr[i]].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 23 ms 8796 KB Output is correct
4 Correct 16 ms 6492 KB Output is correct
5 Correct 22 ms 9448 KB Output is correct
6 Correct 23 ms 9308 KB Output is correct
7 Correct 20 ms 9564 KB Output is correct
8 Correct 23 ms 8796 KB Output is correct
9 Correct 21 ms 11612 KB Output is correct
10 Correct 23 ms 9052 KB Output is correct
11 Correct 23 ms 8716 KB Output is correct
12 Correct 24 ms 9560 KB Output is correct
13 Correct 29 ms 9052 KB Output is correct
14 Correct 28 ms 8924 KB Output is correct
15 Correct 25 ms 9048 KB Output is correct
16 Correct 21 ms 10328 KB Output is correct
17 Correct 22 ms 9564 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2580 ms 413136 KB Output is correct
2 Correct 2553 ms 417368 KB Output is correct
3 Correct 2575 ms 417136 KB Output is correct
4 Correct 2460 ms 415128 KB Output is correct
5 Correct 2483 ms 417620 KB Output is correct
6 Correct 2697 ms 445420 KB Output is correct
7 Correct 2694 ms 445828 KB Output is correct
8 Correct 2650 ms 445040 KB Output is correct
9 Correct 153 ms 8012 KB Output is correct
10 Execution timed out 3488 ms 524288 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1712 ms 282540 KB Output is correct
2 Correct 573 ms 107436 KB Output is correct
3 Correct 1746 ms 299984 KB Output is correct
4 Correct 1725 ms 284656 KB Output is correct
5 Correct 150 ms 8120 KB Output is correct
6 Correct 1798 ms 292228 KB Output is correct
7 Correct 1645 ms 280664 KB Output is correct
8 Correct 1596 ms 274700 KB Output is correct
9 Correct 1615 ms 274612 KB Output is correct
10 Correct 1597 ms 271172 KB Output is correct
11 Correct 1537 ms 266824 KB Output is correct
12 Correct 1495 ms 255256 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2580 ms 413136 KB Output is correct
2 Correct 2553 ms 417368 KB Output is correct
3 Correct 2575 ms 417136 KB Output is correct
4 Correct 2460 ms 415128 KB Output is correct
5 Correct 2483 ms 417620 KB Output is correct
6 Correct 2697 ms 445420 KB Output is correct
7 Correct 2694 ms 445828 KB Output is correct
8 Correct 2650 ms 445040 KB Output is correct
9 Correct 153 ms 8012 KB Output is correct
10 Execution timed out 3488 ms 524288 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 23 ms 8796 KB Output is correct
4 Correct 16 ms 6492 KB Output is correct
5 Correct 22 ms 9448 KB Output is correct
6 Correct 23 ms 9308 KB Output is correct
7 Correct 20 ms 9564 KB Output is correct
8 Correct 23 ms 8796 KB Output is correct
9 Correct 21 ms 11612 KB Output is correct
10 Correct 23 ms 9052 KB Output is correct
11 Correct 23 ms 8716 KB Output is correct
12 Correct 24 ms 9560 KB Output is correct
13 Correct 29 ms 9052 KB Output is correct
14 Correct 28 ms 8924 KB Output is correct
15 Correct 25 ms 9048 KB Output is correct
16 Correct 21 ms 10328 KB Output is correct
17 Correct 22 ms 9564 KB Output is correct
18 Correct 2580 ms 413136 KB Output is correct
19 Correct 2553 ms 417368 KB Output is correct
20 Correct 2575 ms 417136 KB Output is correct
21 Correct 2460 ms 415128 KB Output is correct
22 Correct 2483 ms 417620 KB Output is correct
23 Correct 2697 ms 445420 KB Output is correct
24 Correct 2694 ms 445828 KB Output is correct
25 Correct 2650 ms 445040 KB Output is correct
26 Correct 153 ms 8012 KB Output is correct
27 Execution timed out 3488 ms 524288 KB Time limit exceeded
28 Halted 0 ms 0 KB -