oj.uz

답안 #269304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
269304 2020-08-17T06:22:08 Z gs14004(#5122) 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 8 ms 12032 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 100005;
const int mod = 1e9 + 7;

int n, m;
pi a[MAXN];

int pa[MAXN];
vector<int> memb[MAXN];
set<int> out[MAXN], in[MAXN];

lint fade = 0;

void uni(int x, int y){
	x = pa[x];
	y = pa[y];
	if(x == y) return;
	fade += 2 * sz(memb[x]) * sz(memb[y]);
	if(sz(memb[x]) + sz(in[x]) < sz(memb[y]) + sz(in[y])){
		swap(x, y);
	}
	vector<pi> que;
	for(auto &i : memb[y]){
		pa[i] = x;
		memb[x].push_back(i);
		if(out[i].find(x) != out[i].end()){
			out[i].erase(x);
		}
		for(auto &j : out[i]){ // v(i) -> comp(j)
			if(in[x].find(j) != in[x].end()) que.emplace_back(j, x);
		}
	}
	for(auto &i : in[y]){
		out[i].erase(y);
		if(x != pa[i] && out[i].find(x) == out[i].end()){
			out[i].insert(x);
			in[x].insert(i);
			// v(i) -> comp(y)
			if(in[pa[i]].find(x) != in[pa[i]].end()) que.emplace_back(x, i);
		}
	}
	memb[y].clear();
	in[y].clear();
	for(auto &[x, y] : que) uni(x, y);
}

void add_edge(int x, int y){
	if(pa[x] != pa[y]){
		out[x].insert(pa[y]);
		in[pa[y]].insert(x);
	}
}

int main(){
	set<pi> edg;
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		memb[i].push_back(i);
		pa[i] = i;
	}
	for(int i=0; i<m; i++){
		int x, y; scanf("%d %d",&x,&y);
		x--; y--;
		if(edg.find(pi(y, x)) != edg.end()){
			uni(x, y);
		}
		add_edge(x, y);
		edg.emplace(x, y);
		lint ret = fade;
		for(int j=0; j<n; j++){
			for(auto &k : out[j]){
				ret += sz(memb[k]);
			}
		}
		printf("%lld\n", ret);
	}
}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
joitter2.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   int x, y; scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 12032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 12032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 12032 KB Output isn't correct
2 Halted 0 ms 0 KB -