oj.uz

Submission #909909

# Submission time Handle Problem Language Result Execution time Memory
909909 2024-01-17T15:15:19 Z bachhoangxuan 전압 (JOI14_voltage) C++17
100 / 100
 204 ms 11056 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int mod=1e9+7;
const int maxn=200005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=20;
const int maxa=1000000;
const int root=3;
const int base=101;

int n,m,s[maxn],t[maxn],res;

struct event{
    int pu,pv;
    bool cur;
};

namespace DSU{
    bool check=true;
    int par[maxn],d[maxn],sz[maxn];
    vector<event> E;
    void reset(){
        check=true;E.clear();
        for(int i=1;i<=n;i++) par[i]=i,d[i]=0,sz[i]=1;
    }
    pii findpar(int u){
        if(u!=par[u]){
            pii x=findpar(par[u]);
            return {x.fi,x.se^d[u]};
        }
        return {u,0};
    }

    void unions(int u,int v,int t){
        auto [pu,du]=findpar(u);
        auto [pv,dv]=findpar(v);
        if(pu==pv){
            E.push_back({pu,pv,check});
            if((du^t)!=dv) check=false;
            return;
        }
        if(sz[pu]<sz[pv]) swap(pu,pv),swap(du,dv);
        E.push_back({pu,pv,check});
        par[pv]=pu;sz[pu]+=sz[pv];
        d[pv]^=du^dv^t;
    }
    void roll_back(){
        event e=E.back();
        E.pop_back();
        check=e.cur;
        int pu=e.pu,pv=e.pv;
        if(pu==pv) return;
        d[pv]=0;par[pv]=pv;
        sz[pu]-=sz[pv];
    }
}

void dnc(int l,int r){
    if(l==r){
        DSU::unions(s[l],t[l],0);
        res+=DSU::check;
        DSU::roll_back();
        return;
    }
    int mid=(l+r)>>1;
    for(int i=r;i>mid;i--) DSU::unions(s[i],t[i],1);
    dnc(l,mid);
    for(int i=r;i>mid;i--) DSU::roll_back();
    for(int i=l;i<=mid;i++) DSU::unions(s[i],t[i],1);
    dnc(mid+1,r);
    for(int i=l;i<=mid;i++) DSU::roll_back();
}

void solve(){
    cin >> n >> m;
    DSU::reset();
    for(int i=1;i<=m;i++) cin >> s[i] >> t[i];
    dnc(1,m);
    cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2520 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 3 ms 2780 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 2 ms 2524 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6096 KB Output is correct
2 Correct 99 ms 6096 KB Output is correct
3 Correct 52 ms 6212 KB Output is correct
4 Correct 94 ms 6088 KB Output is correct
5 Correct 8 ms 2908 KB Output is correct
6 Correct 92 ms 6232 KB Output is correct
7 Correct 95 ms 6296 KB Output is correct
8 Correct 105 ms 6096 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5924 KB Output is correct
2 Correct 41 ms 6244 KB Output is correct
3 Correct 43 ms 6100 KB Output is correct
4 Correct 1 ms 2684 KB Output is correct
5 Correct 80 ms 5864 KB Output is correct
6 Correct 77 ms 6228 KB Output is correct
7 Correct 100 ms 6252 KB Output is correct
8 Correct 103 ms 6100 KB Output is correct
9 Correct 102 ms 6280 KB Output is correct
10 Correct 108 ms 6200 KB Output is correct
11 Correct 79 ms 6088 KB Output is correct
12 Correct 93 ms 6084 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8792 KB Output is correct
2 Correct 76 ms 9668 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 123 ms 6276 KB Output is correct
5 Correct 122 ms 6332 KB Output is correct
6 Correct 109 ms 6376 KB Output is correct
7 Correct 182 ms 10448 KB Output is correct
8 Correct 176 ms 9588 KB Output is correct
9 Correct 159 ms 10252 KB Output is correct
10 Correct 143 ms 10184 KB Output is correct
11 Correct 127 ms 9680 KB Output is correct
12 Correct 154 ms 10460 KB Output is correct
13 Correct 146 ms 11056 KB Output is correct
14 Correct 204 ms 9536 KB Output is correct
15 Correct 172 ms 10440 KB Output is correct
16 Correct 168 ms 10440 KB Output is correct
17 Correct 157 ms 9596 KB Output is correct
18 Correct 132 ms 9536 KB Output is correct