Submission #227299

#	Time	Username	Problem	Language	Result	Execution time	Memory
227299		Mercenary	전압 (JOI14_voltage)	C++14	100 / 100	303 ms	13928 KiB

voltage

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e5 + 5;
int lab[maxn];
int col[maxn];
int n , m;
int u[maxn] , v[maxn];
vector<pair<int*,int>> D;
void rollback(int sz){
    while(D.size() > sz){
        (*D.back().first) = D.back().second;
        D.pop_back();
    }
}
void Change(int &u , int v){
    D.pb(mp(&u,u));
    u = v;
}
int res = 0;
pair<int,bool> FindLab(int u){
    if(lab[u] < 0)return mp(u , col[u]);
    auto tmp = FindLab(lab[u]);
    return mp(tmp.first , tmp.second ^ col[u]);
}
bool Merge(int u , int v){
    auto [s , cs] = FindLab(u);
    auto [d , cd] = FindLab(v);
    if(s == d){
        return (cs ^ cd);
    }
    if(lab[s] > lab[d]){
        swap(s , d);swap(cs,cd);
    }
    Change(lab[s],lab[s]+lab[d]);
    Change(lab[d] , s);
    Change(col[d],cs^cd^1);
    return 1;
}

void solve(int l , int r){
//    cout << l << " " << r << endl;
//    for(int i = 1 ; i <= n ; ++i)cout << FindLab(i).second << " ";
//    cout << endl;
    if(l == r){
        auto s = FindLab(u[l]);
        auto d = FindLab(v[l]);
        res += (s.first != d.first || s.second == d.second);
//        cout << (s.first != d.first || s.second == d.second) << endl;
        return;
    }
    int tmp = D.size();
    int mid = l + r >> 1;
    bool ok = 1;
    for(int i = l ; i <= mid && ok ; ++i){
        ok &= Merge(u[i] , v[i]);
    }
    if(ok)solve(mid + 1 , r);
    rollback(tmp);
    ok = 1;
    for(int i = mid + 1 ; i <= r && ok ; ++i){
        ok &= Merge(u[i] , v[i]);
    }
    if(ok)solve(l , mid);
    rollback(tmp);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    fill_n(lab,maxn,-1);
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i){
        cin >> u[i] >> v[i];
    }
    solve(1 , m);
    cout << res;
}

Compilation message (stderr)

voltage.cpp: In function 'void rollback(int)':
voltage.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(D.size() > sz){
           ~~~~~~~~~^~~~
voltage.cpp: In function 'bool Merge(int, int)':
voltage.cpp:40:10: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto [s , cs] = FindLab(u);
          ^
voltage.cpp:41:10: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto [d , cd] = FindLab(v);
          ^
voltage.cpp: In function 'void solve(int, int)':
voltage.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
voltage.cpp: In function 'int main()':
voltage.cpp:85:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
voltage.cpp:86:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45