oj.uz

Submission #972585

# Submission time Handle Problem Language Result Execution time Memory
972585 2024-04-30T16:33:50 Z simona1230 Bridges (APIO19_bridges) C++17
27 / 100
 3000 ms 270000 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=10000;

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]]=i;
        }

        for(int i=1;i<=m;i++)
        {
            if(!used[i])
                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 651 ms 68592 KB Output is correct
4 Correct 46 ms 6840 KB Output is correct
5 Correct 539 ms 79484 KB Output is correct
6 Correct 390 ms 82856 KB Output is correct
7 Correct 705 ms 82256 KB Output is correct
8 Correct 578 ms 63056 KB Output is correct
9 Correct 832 ms 124628 KB Output is correct
10 Correct 611 ms 72136 KB Output is correct
11 Correct 590 ms 68020 KB Output is correct
12 Correct 693 ms 89940 KB Output is correct
13 Correct 690 ms 75768 KB Output is correct
14 Correct 640 ms 67012 KB Output is correct
15 Correct 655 ms 75884 KB Output is correct
16 Correct 669 ms 102908 KB Output is correct
17 Correct 752 ms 92324 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 270000 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 3039 ms 258664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 19968 KB Output is correct
2 Correct 464 ms 8020 KB Output is correct
3 Correct 95 ms 9176 KB Output is correct
4 Correct 68 ms 9432 KB Output is correct
5 Correct 555 ms 22228 KB Output is correct
6 Correct 635 ms 23656 KB Output is correct
7 Correct 568 ms 22044 KB Output is correct
8 Correct 537 ms 21856 KB Output is correct
9 Correct 589 ms 22072 KB Output is correct
10 Correct 564 ms 22116 KB Output is correct
11 Correct 594 ms 22792 KB Output is correct
12 Correct 576 ms 22736 KB Output is correct
13 Correct 605 ms 22744 KB Output is correct
14 Correct 555 ms 22184 KB Output is correct
15 Correct 561 ms 22204 KB Output is correct
16 Correct 693 ms 23760 KB Output is correct
17 Correct 642 ms 23820 KB Output is correct
18 Correct 674 ms 23736 KB Output is correct
19 Correct 674 ms 23696 KB Output is correct
20 Correct 609 ms 23268 KB Output is correct
21 Correct 648 ms 23176 KB Output is correct
22 Correct 643 ms 23344 KB Output is correct
23 Correct 557 ms 20824 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 270000 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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 651 ms 68592 KB Output is correct
4 Correct 46 ms 6840 KB Output is correct
5 Correct 539 ms 79484 KB Output is correct
6 Correct 390 ms 82856 KB Output is correct
7 Correct 705 ms 82256 KB Output is correct
8 Correct 578 ms 63056 KB Output is correct
9 Correct 832 ms 124628 KB Output is correct
10 Correct 611 ms 72136 KB Output is correct
11 Correct 590 ms 68020 KB Output is correct
12 Correct 693 ms 89940 KB Output is correct
13 Correct 690 ms 75768 KB Output is correct
14 Correct 640 ms 67012 KB Output is correct
15 Correct 655 ms 75884 KB Output is correct
16 Correct 669 ms 102908 KB Output is correct
17 Correct 752 ms 92324 KB Output is correct
18 Execution timed out 3029 ms 270000 KB Time limit exceeded
19 Halted 0 ms 0 KB -