Submission #212735

#	Time	Username	Problem	Language	Result	Execution time	Memory
212735		BThero	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	17 / 100	615 ms	24952 KiB

joitter2

#define DBG 1
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (DBG) cerr << #x << " = " << x << endl;

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)5e3;

bitset<MAXN> row[MAXN], col[MAXN], twin[MAXN];
pii Q[MAXN * MAXN];
int ans, sz;
int n, m;

void push() {
    for (int i = 0; i < sz; ++i) {
        int x = Q[i].fi;
        int y = Q[i].se;
        bitset<MAXN> tmp = col[x] ^ col[y];
        
        for (int z = tmp._Find_first(); z < n; z = tmp._Find_next(z)) {
            if (z != x && z != y) {
                ++ans;
            
                if (row[z][x]) {
                    row[z][y] = 1;
                    col[y][z] = 1;
                    
                    if (row[y][z]) {
                        twin[z][y] = twin[y][z] = 1;
                        Q[sz++] = mp(z, y);
                    }
                }
                else {
                    row[z][x] = 1;
                    col[x][z] = 1;
                    
                    if (row[x][z]) {
                        twin[x][z] = twin[z][x] = 1;
                        Q[sz++] = mp(x, z);
                    }
                }
            }
        }
    }
}

void solve() {
	scanf("%d %d", &n, &m);
    
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        
        if (!row[u][v]) {
            ++ans;
            row[u][v] = 1;
            col[v][u] = 1;
            sz = 0;
            
            if (row[v][u]) {
                Q[sz++] = mp(u, v);
                twin[u][v] = twin[v][u] = 1;
            }
            
            bitset<MAXN> tmp = twin[v] & ~row[u];
            
            for (int w = tmp._Find_first(); w < n; w = tmp._Find_next(w)) {
                if (w != v && w != u) {
                    ++ans;
                    row[u][w] = col[w][u] = 1;
                    
                    if (row[w][u]) {
                        Q[sz++] = mp(u, w);
                        twin[u][w] = twin[w][u] = 1;
                    }
                }
            }
            
            push();
        }
    
        printf("%d\n", ans);
    }
}

int main() {
	int tt = 1;
	
	while (tt--) {
		solve();
	}

	return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void solve()':
joitter2.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 0 / 83