Submission #105702

#	Time	Username	Problem	Language	Result	Execution time	Memory
105702		Pro_ktmr	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	272 ms	13128 KiB

friends

#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

int N,M;
vector<pair<int,int> > allows[100000];

struct UnionFind{
public:
	int parent[100000];
	int N;
	void reset(int n){
		N = n;
		for(int i=0; i<N; i++) parent[i] = i;
	}
	int root(int a){
		if(parent[a] == a) return a;
		else return parent[a] = root(parent[a]);
	}
	void add(int a, int b){
		if(root(a) == root(b)) return;
		parent[b] = a;
	}
};

bool already[100000] = {};
int parent[100000];
LL c[100000] = {};
bool isOK[100000] = {};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << setprecision(9);

	cin >> N >> M;
	for(int i=0; i<M; i++){
		int A,B;
		cin >> A >> B;
		A--; B--;
		allows[A].push_back(MP(B,0));
		allows[B].push_back(MP(A,1));
	}

	UnionFind uf;
	uf.reset(N);
	queue<int> que;
	for(int i=0; i<N; i++){
		if(already[i]) continue;
		already[i] = true;
		c[i] = 1;
		que.push(i);
		while(!que.empty()){
			int now = que.front();
			que.pop();
			for(int j=0; j<allows[now].size(); j++){
				if(!already[allows[now][j].first]){
					already[allows[now][j].first] = true;
					uf.add(i,allows[now][j].first);
					c[i]++;
					que.push(allows[now][j].first);
				}
			}
		}
	}

	for(int i=0; i<N; i++){
		int co = 0;
		for(int j=0; j<allows[i].size(); j++){
			if(allows[i][j].second == 0) co++;
		}
		if(co < 2) continue;
		for(int j=0; j<allows[i].size(); j++){
			if(allows[i][j].second == 0){
				if(!isOK[allows[i][j].first]) que.push(allows[i][j].first);
				isOK[allows[i][j].first] = true;
			}
		}
	}
	while(!que.empty()){
		int now = que.front();
		que.pop();
		for(int i=0; i<allows[now].size(); i++){
			if(allows[now][i].second == 0 && !isOK[allows[now][i].first]){
				isOK[allows[now][i].first] = true;
				que.push(allows[now][i].first);
			}
		}
	}

	LL ans = 0;
	for(int i=0; i<N; i++){
		if(!isOK[i]){
			c[uf.root(i)]--;
			for(int j=0; j<allows[i].size(); j++){
				if(allows[i][j].second == 0) ans++;
			}
		}
	}
	for(int i=0; i<N; i++){
		ans += c[i]*(c[i]-1);
	}
	cout << ans << endl;

	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<allows[now].size(); j++){
                 ~^~~~~~~~~~~~~~~~~~~
friends.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<allows[i].size(); j++){
                ~^~~~~~~~~~~~~~~~~
friends.cpp:101:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<allows[i].size(); j++){
                ~^~~~~~~~~~~~~~~~~
friends.cpp:111:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<allows[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~
friends.cpp:123:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<allows[i].size(); j++){
                 ~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65