oj.uz

Submission #421394

# Submission time Handle Problem Language Result Execution time Memory
421394 2021-06-09T06:37:17 Z 조영욱(#7654) Collapse (JOI18_collapse) C++17
30 / 100
 198 ms 31416 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

int comp;
typedef pair<int,int> P;
vector<int> vec[100000];
const int sz=131072;
vector<P> seg[sz*2];
map<P,int> mp;
typedef pair<P,P> PP;
stack<PP> s;
int ret[sz];

void insert(int l,int r,P val,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return;
    }
    if (l<=nodel&&noder<=r) {
        seg[node].push_back(val);
        return;
    }
    int mid=(nodel+noder)/2;
    insert(l,r,val,node*2,nodel,mid);
    insert(l,r,val,node*2+1,mid+1,noder);
}

int p[100000];
int lv[100000];

int find(int a) {
    if (p[a]<0) {
        return a;
    }
    return find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    if (lv[a]<lv[b]) {
        swap(a,b);
    }
    s.push(PP(P(a,lv[a]),P(b,p[b])));
    p[b]=a;
    if (lv[a]==lv[b]) {
        lv[a]++;
    }
    comp--;
}

void func(int node) {
    PP now=s.top();
    for(int i=0;i<seg[node].size();i++) {
        merge(seg[node][i].first,seg[node][i].second);
    }
    if (node>=sz) {
        ret[node-sz]=comp;
    }
    else {
        func(node*2);
        func(node*2+1);
    }
    while (s.top()!=now) {
        lv[s.top().first.first]=s.top().first.second;
        p[s.top().second.first]=s.top().second.second;
        comp++;
        s.pop();
    }
}

vector<int> simulateCollapse(int n,vector<int> t,vector<int> x,vector<int> y,vector<int> w,vector<int> pp) {
    comp=n;
    memset(p,-1,sizeof(p));
    int c=t.size();
    int q=w.size();
    for(int i=0;i<q;i++) {
        vec[w[i]].push_back(i);
    }
    for(int i=0;i<c;i++) {
        if (x[i]>y[i]) {
            swap(x[i],y[i]);
        }
        if (x[i]<=pp[0]&&y[i]>pp[0]) {
            continue;
        }
        if (t[i]==0) {
            mp[P(x[i],y[i])]=i;
        }
        else {
            insert(mp[P(x[i],y[i])],i-1,P(x[i],y[i]));
            mp.erase(P(x[i],y[i]));
        }
    }
    for(auto curr:mp) {
        insert(curr.second,c-1,curr.first);
    }
    vector<int> v(q);
    s.push(PP(P(-1,-1),P(-1,-1)));
    func(1);
    for(int i=0;i<q;i++) {
        v[i]=ret[w[i]];
    }
    return v;
}

Compilation message

collapse.cpp: In function 'void func(int)':
collapse.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i<seg[node].size();i++) {
      |                 ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10060 KB Output is correct
2 Incorrect 10 ms 9876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12544 KB Output is correct
2 Correct 45 ms 12652 KB Output is correct
3 Correct 98 ms 20988 KB Output is correct
4 Correct 37 ms 12864 KB Output is correct
5 Correct 114 ms 22024 KB Output is correct
6 Correct 48 ms 13784 KB Output is correct
7 Correct 195 ms 30280 KB Output is correct
8 Correct 119 ms 22788 KB Output is correct
9 Correct 48 ms 12860 KB Output is correct
10 Correct 40 ms 12904 KB Output is correct
11 Correct 43 ms 13820 KB Output is correct
12 Correct 145 ms 23928 KB Output is correct
13 Correct 180 ms 27612 KB Output is correct
14 Correct 198 ms 31416 KB Output is correct
15 Correct 188 ms 30420 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12600 KB Output is correct
2 Incorrect 38 ms 12492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10060 KB Output is correct
2 Incorrect 10 ms 9876 KB Output isn't correct
3 Halted 0 ms 0 KB -