oj.uz

Submission #1032796

# Submission time Handle Problem Language Result Execution time Memory
1032796 2024-07-24T08:48:58 Z vjudge1 Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 20216 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);
    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);
}
set<int>adj[5000],adj2[5000];
bitset<5000>vis;
map<pair<int,int>,int> mp;
void dfs(int n){
    if(vis[n])return;
    vis[n]=1;
    for(auto i:adj2[n])  
        dfs(i);
}
int calc(int N){
    int ans=0;
    for(int i=0;i<N;i++)
        if(!vis[i])
            dfs(i),ans++;
    vis.reset();
    return ans;
}
void setedg(int nod,int N){
    for(int i=0;i<N;i++)
        adj2[i]=adj[i];
    for(int i=0;i<=nod;i++) {
        while(adj2[i].size()) {
            int k=*--adj2[i].end();
            if(k<=nod)break;
            adj2[i].erase(k);
            adj2[k].erase(i);
        }
    }
}
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();
    vector<int>v=W;
    for(int i=0;i<K;i++){
        int t=T[i];
        if(!t){
            assert(!adj[X[i]].count(Y[i]));
            adj[X[i]].insert(Y[i]);
            adj[Y[i]].insert(X[i]);
        } else {
            assert(adj[X[i]].count(Y[i]));
            adj[X[i]].erase(Y[i]);
            adj[Y[i]].erase(X[i]);
        }
        for(int h=0;h<W.size();h++){
            if(W[h]==i)
                setedg(P[h],N),v[h]=calc(N);
        }
    }
    for(int i=0;i<N;i++)
        adj[i].clear();
    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);
      |                     ~~~^~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int h=0;h<W.size();h++){
      |                     ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14172 KB Output is correct
2 Correct 7 ms 13916 KB Output is correct
3 Correct 9 ms 14096 KB Output is correct
4 Correct 12 ms 13916 KB Output is correct
5 Correct 35 ms 14172 KB Output is correct
6 Correct 1164 ms 15204 KB Output is correct
7 Correct 238 ms 14112 KB Output is correct
8 Correct 247 ms 13912 KB Output is correct
9 Correct 284 ms 14172 KB Output is correct
10 Correct 418 ms 14416 KB Output is correct
11 Correct 1393 ms 15500 KB Output is correct
12 Correct 1357 ms 15076 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15960 KB Output is correct
2 Correct 34 ms 16184 KB Output is correct
3 Correct 6213 ms 19680 KB Output is correct
4 Correct 108 ms 16220 KB Output is correct
5 Correct 6730 ms 20216 KB Output is correct
6 Execution timed out 15024 ms 18112 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16216 KB Output is correct
2 Correct 39 ms 16188 KB Output is correct
3 Correct 64 ms 16396 KB Output is correct
4 Correct 125 ms 16216 KB Output is correct
5 Correct 1325 ms 16908 KB Output is correct
6 Execution timed out 15059 ms 17572 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14172 KB Output is correct
2 Correct 7 ms 13916 KB Output is correct
3 Correct 9 ms 14096 KB Output is correct
4 Correct 12 ms 13916 KB Output is correct
5 Correct 35 ms 14172 KB Output is correct
6 Correct 1164 ms 15204 KB Output is correct
7 Correct 238 ms 14112 KB Output is correct
8 Correct 247 ms 13912 KB Output is correct
9 Correct 284 ms 14172 KB Output is correct
10 Correct 418 ms 14416 KB Output is correct
11 Correct 1393 ms 15500 KB Output is correct
12 Correct 1357 ms 15076 KB Output is correct
13 Correct 28 ms 15960 KB Output is correct
14 Correct 34 ms 16184 KB Output is correct
15 Correct 6213 ms 19680 KB Output is correct
16 Correct 108 ms 16220 KB Output is correct
17 Correct 6730 ms 20216 KB Output is correct
18 Execution timed out 15024 ms 18112 KB Time limit exceeded
19 Halted 0 ms 0 KB -