Submission #221464

#	Time	Username	Problem	Language	Result	Execution time	Memory
221464		patrikpavic2	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1619 ms	91468 KiB

joitter2

#include <cstdio>
#include <vector>
#include <map>
#include <queue>

#define PB push_back
#define X first
#define Y second

using namespace std;

const int N = 1e5 + 500;

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

vector < int > mene[N];
vector < pii > ja[N];
map < int, int > ima[N];
map < int, int > grp[N];

int par[N], n, m, oduz[N], siz[N];
int vel[N];
queue < int > spoji_X, spoji_Y;

int pr(int x){
	if(x == par[x]) return x;
	return par[x] = pr(par[x]);
}


ll sol = 0;

void spoji(int x,int y){
	x = pr(x), y = pr(y);
	if(x == y) return;
	if((int)mene[x].size() + (int)ja[x].size() < (int)mene[y].size() + (int)ja[y].size())
		swap(x, y);
	int pres = 0;
	for(int z : mene[y]){
		if(pr(z) == x || pr(z) == y) 
			continue;
		if(!ima[z][y]) continue;
		ima[z][y] = 0;
		grp[pr(z)][y]--;
		if(ima[z][x]){
			pres++;
		}
		else{
			ima[z][x] = 1;
			grp[pr(z)][x]++;
			mene[x].PB(z);
		}
		if(grp[pr(z)][x] && grp[x][pr(z)]){
			spoji_X.push(x); spoji_Y.push(pr(z));
		}
	}
	
	map < pii , int > duplici;
	
	for(pii tmp : ja[y]){
		int z = tmp.Y, w = tmp.X;
		if(pr(z) == x || pr(z) == y) continue;
		if(duplici[{w, pr(z)}]) continue;
		duplici[{w, pr(z)}] = 1;
		grp[y][pr(z)]--;
		grp[x][pr(z)]++;
		ja[x].PB(tmp);
		if(grp[pr(z)][x] && grp[x][pr(z)]){
			spoji_X.push(x); spoji_Y.push(pr(z));
		}
	}
	sol += (ll)(vel[y] - grp[x][y] - pres) * (ll)siz[x];
	sol += (ll)(vel[x] - grp[y][x] - pres) * (ll)siz[y];
	sol += 2LL * siz[x] * siz[y] - (ll)grp[y][x] * siz[x] - (ll)grp[x][y] * siz[y];
	vel[x] = vel[x] + vel[y] - grp[x][y] - grp[y][x] - pres;
	siz[x] = siz[x] + siz[y];
	par[y] = x;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++)
		par[i] = i, siz[i] = 1;
	for(int j = 0;j < m;j++){
		int x, y; scanf("%d%d", &x, &y);
		if(ima[x][pr(y)] || pr(x) == pr(y)){
			printf("%lld\n", sol);
			continue;		
		}
		if(!grp[pr(y)][pr(x)]){
			mene[pr(y)].PB(x);
			ima[x][pr(y)]++;
			grp[pr(x)][pr(y)]++;
			sol += siz[pr(y)]; 
			vel[pr(y)]++;
			printf("%lld\n", sol);
			ja[pr(x)].PB({x, y});
			continue;
		}
		x = pr(x), y = pr(y);
		spoji(x, y);
		for(;!spoji_X.empty();){
			spoji(spoji_X.front(), spoji_Y.front());
			spoji_X.pop(), spoji_Y.pop();
		}
		printf("%lld\n", sol);
	}
}

Compilation message (stderr)

joitter2.cpp: In function 'int main()':
joitter2.cpp:82: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:86:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

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