oj.uz

Submission #1032735

# Submission time Handle Problem Language Result Execution time Memory
1032735 2024-07-24T07:19:52 Z vjudge1 Collapse (JOI18_collapse) C++17
0 / 100
 16 ms 16116 KB 
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
struct dsurol{
    int par[100100],dep[100100],ans;
    stack<pair<int,int>>stk;
    dsurol(){memset(par,0,sizeof par);memset(dep,0,sizeof dep);ans=0;}
    void init(int n){
        ans=n;
    }
    int abp(int n){
        return par[n]?abp(par[n]):n;
    }
    void merge(int a,int b){
        a=abp(++a);
        b=abp(++b);
        if(a-b){
            ans--;
            if(dep[a]<dep[b])
                swap(a,b);
            par[b]=a;
            stk.push({b,dep[a]});
            dep[a]=max(dep[a],dep[b]+1);
        }
    }
    void rerol(){
        auto[b,prvd]=stk.top();
        stk.pop();
        dep[par[b]]=prvd;
        par[b]=0;
        ans++;
    }
    void rolbak(int n){
        while(stk.size()>n)
            rerol();
    }
} dsu;
vector<pair<int,int>>whattoad[1<<19];
void add(int i,int l,int r,int ll,int rr,pair<int,int>K){
    if(ll<=l&&r<=rr)
        return whattoad[i].push_back(K);
    if(ll>r||l>rr) return;
    add(i*2,l,l+r>>1,ll,rr,K);
    add(i*2+1,l+r+2>>1,r,ll,rr,K);
}
vector<int>ans;
void solve(int i,int l,int r){
    int k=dsu.stk.size();
    for(auto&[a,b]:whattoad[i])
        dsu.merge(a,b);
    whattoad[i].clear();
    if(l==r)
        ans.push_back(dsu.ans);
    else solve(i*2,l,l+r>>1),
        solve(i*2+1,l+r+2>>1,r);
    dsu.rolbak(k);
}
map<pair<int,int>,int> mp;
std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P) {
    dsu.init(N);
    int K=T.size();
    int c=P[0];
    for(int i=0;i<K;i++){
        int t=T[i];
        if(X[i]>Y[i])swap(X[i],Y[i]);
        if(X[i]<=c&&Y[i]>c)continue;
        if(!t){
            mp[{X[i],Y[i]}]=i+1;
        } else {
            add(1,1,K,mp[{X[i],Y[i]}],i,{X[i],Y[i]});
            mp.erase({X[i],Y[i]});
        }
    }
    for(auto[k,y]:mp)
        add(1,1,K,y,K,k);
    mp.clear();
    ans.clear();
    solve(1,1,K);
    vector<int>v;
    for(auto i:W)
        v.push_back(ans[i-1]);
    return v;
}

Compilation message

collapse.cpp: In member function 'void dsurol::rolbak(int)':
collapse.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         while(stk.size()>n)
      |               ~~~~~~~~~~^~
collapse.cpp: In function 'void add(int, int, int, int, int, std::pair<int, int>)':
collapse.cpp:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     add(i*2,l,l+r>>1,ll,rr,K);
      |               ~^~
collapse.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     add(i*2+1,l+r+2>>1,r,ll,rr,K);
      |               ~~~^~
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:54:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     else solve(i*2,l,l+r>>1),
      |                      ~^~
collapse.cpp:55:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         solve(i*2+1,l+r+2>>1,r);
      |                     ~~~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 15976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 16116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13656 KB Output isn't correct
2 Halted 0 ms 0 KB -