oj.uz

Submission #227299

# Submission time Handle Problem Language Result Execution time Memory
227299 2020-04-26T17:25:15 Z Mercenary 전압 (JOI14_voltage) C++14
100 / 100
 303 ms 13928 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 7 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 6 ms 1280 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 6 ms 1280 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 6 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11884 KB Output is correct
2 Correct 215 ms 12008 KB Output is correct
3 Correct 48 ms 11880 KB Output is correct
4 Correct 49 ms 11880 KB Output is correct
5 Correct 17 ms 2556 KB Output is correct
6 Correct 199 ms 11880 KB Output is correct
7 Correct 200 ms 11888 KB Output is correct
8 Correct 209 ms 11880 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 11368 KB Output is correct
2 Correct 119 ms 11752 KB Output is correct
3 Correct 112 ms 11752 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 150 ms 7260 KB Output is correct
6 Correct 166 ms 11880 KB Output is correct
7 Correct 190 ms 11880 KB Output is correct
8 Correct 169 ms 11880 KB Output is correct
9 Correct 202 ms 11888 KB Output is correct
10 Correct 179 ms 11880 KB Output is correct
11 Correct 57 ms 11880 KB Output is correct
12 Correct 122 ms 11880 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 12948 KB Output is correct
2 Correct 131 ms 13800 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 200 ms 12008 KB Output is correct
5 Correct 211 ms 12008 KB Output is correct
6 Correct 161 ms 12056 KB Output is correct
7 Correct 303 ms 13800 KB Output is correct
8 Correct 247 ms 13800 KB Output is correct
9 Correct 223 ms 13928 KB Output is correct
10 Correct 232 ms 13800 KB Output is correct
11 Correct 58 ms 9668 KB Output is correct
12 Correct 79 ms 13800 KB Output is correct
13 Correct 121 ms 13800 KB Output is correct
14 Correct 302 ms 13800 KB Output is correct
15 Correct 70 ms 13800 KB Output is correct
16 Correct 237 ms 13672 KB Output is correct
17 Correct 250 ms 9708 KB Output is correct
18 Correct 203 ms 9708 KB Output is correct