oj.uz

Submission #859213

# Submission time Handle Problem Language Result Execution time Memory
859213 2023-10-10T01:38:39 Z TS_2392 Making Friends on Joitter is Fun (JOI20_joitter2) C++14
100 / 100
 888 ms 68436 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
// using namespace __gnu_pbds;

#define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED         ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL            cout << '\n'
#define dbg(x)        cout << #x << " = " << (x) << ' '
#define dbgp(x)       cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}

#define epl           emplace
#define pb            push_back
#define eb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair

#define sqr(x)        ((x) * (x))
#define all(x)        (x).begin(), (x).end()
#define rall(x)       (x).rbegin(), (x).rend()
#define lwb           lower_bound
#define upb           upper_bound

#define clz           __builtin_clzll // or __builtin_clz
#define ctz           __builtin_ctzll // or __builtin_ctz
#define pct           __builtin_popcountll // or __builtin_popcount

typedef long long            ll;
typedef long double          ldb;
typedef unsigned int         uint;
typedef unsigned long long   ull;
typedef pair<ll, ll>         pll;
typedef pair<ll, int>        pli;
typedef pair<int, ll>        pil;
typedef pair<int, int>       pii;
typedef pair<ldb, ldb>       pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
template<class T> void remDup(vector<T> &v){sort(all(v)); v.erase(unique(all(v)),v.end());}

// int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int N = 1e5 + 3;
ll res;
int n, m, pr[N];
queue<pii> to_merge;
set<int> follower[N], adj[N], radj[N];
void add_big_edge(int u, int v){
    //them canh giua nhung thanh phan lien thong
    adj[u].insert(v); radj[v].insert(u);
    if(adj[v].count(u)) to_merge.push({u, v});
}
int find_set(int u){
    return pr[u] < 0 ? u : pr[u] = find_set(pr[u]);
}
int component_sz(int u){
    //component_sz(u) <= 2 * follower[u].size() vi vay dpt la O(M * 2 * log^2(N))
    return follower[u].size() + adj[u].size() + radj[u].size();
}
void unite(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if(u == v) return;
    if(component_sz(u) < component_sz(v)) swap(u, v);

    res += 1LL * (-pr[u]) * follower[v].size() + 1LL * (-pr[v]) * follower[u].size();
    pr[u] += pr[v]; pr[v] = u;

    for(int x : follower[v]){
        if(follower[u].count(x)) res -= (-pr[u]);
        else follower[u].insert(x);
    }
    adj[u].erase(v); radj[u].erase(v);
    adj[v].erase(u); radj[v].erase(u);
    for(int x : adj[v]){
        radj[x].erase(v);
        add_big_edge(u, x);
    }
    for(int x : radj[v]){
        adj[x].erase(v);
        add_big_edge(x, u);
    }
}
void TS_2392(){
    cin >> n >> m;
    memset(pr, 255, sizeof(pr));
    for(int i = 1; i <= n; ++i){
        follower[i].insert(i);
    }
    for(int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        int root_u = find_set(u);
        int root_v = find_set(v);
        if(root_u == root_v || follower[root_v].count(u)){
            cout << res << '\n';
            continue;
        }
        res += -pr[root_v];
        follower[root_v].insert(u);
        add_big_edge(root_u, root_v);

        while(!to_merge.empty()){
            int u, v;
            tie(u, v) = to_merge.front();
            to_merge.pop(); unite(u, v);
        }
        cout << res << '\n';
    }
}
int main(){
    SPEED; fileIO("text");
    int numtest = 1; //cin >> numtest;
    for(int itest = 1; itest <= numtest; ++itest){
        // cout << "Case #" << itest << ": ";
        TS_2392(); //cout << '\n';
    }
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * small cases, special cases (n = 1 ???)
 * do something instead of nothing: code bruteforce
 * WRITE STUFF DOWN and STAY ORGANIZED
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:120:12: note: in expansion of macro 'fileIO'
  120 |     SPEED; fileIO("text");
      |            ^~~~~~
joitter2.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joitter2.cpp:120:12: note: in expansion of macro 'fileIO'
  120 |     SPEED; fileIO("text");
      |            ^~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14704 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 4 ms 14860 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14808 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 3 ms 14780 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 5 ms 14940 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 3 ms 14940 KB Output is correct
24 Correct 3 ms 14936 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 3 ms 14936 KB Output is correct
29 Correct 3 ms 14940 KB Output is correct
30 Correct 3 ms 14940 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 3 ms 14724 KB Output is correct
33 Correct 4 ms 14940 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14704 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 4 ms 14860 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14808 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 3 ms 14780 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 5 ms 14940 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 3 ms 14940 KB Output is correct
24 Correct 3 ms 14936 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 3 ms 14936 KB Output is correct
29 Correct 3 ms 14940 KB Output is correct
30 Correct 3 ms 14940 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 3 ms 14724 KB Output is correct
33 Correct 4 ms 14940 KB Output is correct
34 Correct 5 ms 15196 KB Output is correct
35 Correct 58 ms 20708 KB Output is correct
36 Correct 79 ms 23588 KB Output is correct
37 Correct 77 ms 23576 KB Output is correct
38 Correct 73 ms 23036 KB Output is correct
39 Correct 5 ms 15084 KB Output is correct
40 Correct 7 ms 15452 KB Output is correct
41 Correct 6 ms 15704 KB Output is correct
42 Correct 5 ms 15196 KB Output is correct
43 Correct 6 ms 15196 KB Output is correct
44 Correct 6 ms 15196 KB Output is correct
45 Correct 6 ms 15448 KB Output is correct
46 Correct 6 ms 15192 KB Output is correct
47 Correct 6 ms 15448 KB Output is correct
48 Correct 6 ms 15452 KB Output is correct
49 Correct 11 ms 16220 KB Output is correct
50 Correct 83 ms 24076 KB Output is correct
51 Correct 8 ms 15452 KB Output is correct
52 Correct 66 ms 21776 KB Output is correct
53 Correct 11 ms 15964 KB Output is correct
54 Correct 72 ms 22656 KB Output is correct
55 Correct 7 ms 15708 KB Output is correct
56 Correct 8 ms 15712 KB Output is correct
57 Correct 7 ms 15452 KB Output is correct
58 Correct 7 ms 15448 KB Output is correct
59 Correct 6 ms 15708 KB Output is correct
60 Correct 56 ms 20624 KB Output is correct
61 Correct 6 ms 15448 KB Output is correct
62 Correct 74 ms 23124 KB Output is correct

Subtask #3
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14704 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 5 ms 14940 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 4 ms 14860 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14808 KB Output is correct
12 Correct 3 ms 14940 KB Output is correct
13 Correct 4 ms 14940 KB Output is correct
14 Correct 3 ms 14780 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 5 ms 14940 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 4 ms 14940 KB Output is correct
22 Correct 4 ms 14940 KB Output is correct
23 Correct 3 ms 14940 KB Output is correct
24 Correct 3 ms 14936 KB Output is correct
25 Correct 4 ms 14940 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 4 ms 14940 KB Output is correct
28 Correct 3 ms 14936 KB Output is correct
29 Correct 3 ms 14940 KB Output is correct
30 Correct 3 ms 14940 KB Output is correct
31 Correct 4 ms 14940 KB Output is correct
32 Correct 3 ms 14724 KB Output is correct
33 Correct 4 ms 14940 KB Output is correct
34 Correct 5 ms 15196 KB Output is correct
35 Correct 58 ms 20708 KB Output is correct
36 Correct 79 ms 23588 KB Output is correct
37 Correct 77 ms 23576 KB Output is correct
38 Correct 73 ms 23036 KB Output is correct
39 Correct 5 ms 15084 KB Output is correct
40 Correct 7 ms 15452 KB Output is correct
41 Correct 6 ms 15704 KB Output is correct
42 Correct 5 ms 15196 KB Output is correct
43 Correct 6 ms 15196 KB Output is correct
44 Correct 6 ms 15196 KB Output is correct
45 Correct 6 ms 15448 KB Output is correct
46 Correct 6 ms 15192 KB Output is correct
47 Correct 6 ms 15448 KB Output is correct
48 Correct 6 ms 15452 KB Output is correct
49 Correct 11 ms 16220 KB Output is correct
50 Correct 83 ms 24076 KB Output is correct
51 Correct 8 ms 15452 KB Output is correct
52 Correct 66 ms 21776 KB Output is correct
53 Correct 11 ms 15964 KB Output is correct
54 Correct 72 ms 22656 KB Output is correct
55 Correct 7 ms 15708 KB Output is correct
56 Correct 8 ms 15712 KB Output is correct
57 Correct 7 ms 15452 KB Output is correct
58 Correct 7 ms 15448 KB Output is correct
59 Correct 6 ms 15708 KB Output is correct
60 Correct 56 ms 20624 KB Output is correct
61 Correct 6 ms 15448 KB Output is correct
62 Correct 74 ms 23124 KB Output is correct
63 Correct 454 ms 67308 KB Output is correct
64 Correct 447 ms 67412 KB Output is correct
65 Correct 425 ms 67156 KB Output is correct
66 Correct 162 ms 33360 KB Output is correct
67 Correct 314 ms 60316 KB Output is correct
68 Correct 150 ms 33364 KB Output is correct
69 Correct 273 ms 34384 KB Output is correct
70 Correct 169 ms 33304 KB Output is correct
71 Correct 183 ms 33748 KB Output is correct
72 Correct 322 ms 44372 KB Output is correct
73 Correct 321 ms 46048 KB Output is correct
74 Correct 888 ms 68192 KB Output is correct
75 Correct 406 ms 41220 KB Output is correct
76 Correct 580 ms 53384 KB Output is correct
77 Correct 578 ms 53476 KB Output is correct
78 Correct 168 ms 36824 KB Output is correct
79 Correct 307 ms 41576 KB Output is correct
80 Correct 158 ms 35872 KB Output is correct
81 Correct 249 ms 39248 KB Output is correct
82 Correct 613 ms 53884 KB Output is correct
83 Correct 609 ms 53908 KB Output is correct
84 Correct 496 ms 52852 KB Output is correct
85 Correct 449 ms 52584 KB Output is correct
86 Correct 270 ms 66024 KB Output is correct
87 Correct 266 ms 68436 KB Output is correct
88 Correct 342 ms 45252 KB Output is correct
89 Correct 548 ms 51120 KB Output is correct