oj.uz

답안 #1032522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032522 2024-07-23T23:21:03 Z vjudge1 Collapse (JOI18_collapse) C++17
0 / 100
 15 ms 8408 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[a,b]=stk.top();
        stk.pop();
        dep[par[a]]=b;
        par[a]=0;
        ans++;
    }
    void rolbak(int n){
        while(stk.size()>n)
            rerol();
    }
} dsu;
vector<pair<int,int>>whattoad[200100];
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);
    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],x=X[i],y=Y[i];
        if(x>y)swap(x,y);
        if(x<=c&&y>c)continue;
        if(!t){
            mp[{X[i],Y[i]}]=i+1;
        } else {
            add(1,1,K,mp[{X[i],Y[i]}],i-1,{X[i],Y[i]});
            mp.erase({X[i],Y[i]});
        }
    }
    for(auto[k,x]:mp)
        add(1,1,K,x,K,k);
    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:53:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     else solve(i*2,l,l+r>>1),
      |                      ~^~
collapse.cpp:54:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         solve(i*2+1,l+r+2>>1,r);
      |                     ~~~^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 8408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 8408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 6232 KB Output isn't correct
2 Halted 0 ms 0 KB -