Submission #105702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
105702	2019-04-14T04:15:46 Z	Pro_ktmr	우호 조약 체결 (JOI14_friends)	C++14	100 / 100	272 ms	13128 KB

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

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2916 KB	Output is correct
2	Correct	6 ms	2816 KB	Output is correct
3	Correct	0 ms	2688 KB	Output is correct
4	Correct	5 ms	2688 KB	Output is correct
5	Correct	5 ms	2780 KB	Output is correct
6	Correct	5 ms	2716 KB	Output is correct
7	Correct	5 ms	2688 KB	Output is correct
8	Correct	6 ms	2748 KB	Output is correct
9	Correct	6 ms	2688 KB	Output is correct
10	Correct	6 ms	2660 KB	Output is correct
11	Correct	6 ms	2768 KB	Output is correct
12	Correct	5 ms	2756 KB	Output is correct
13	Correct	5 ms	2660 KB	Output is correct
14	Correct	4 ms	2688 KB	Output is correct
15	Correct	5 ms	2720 KB	Output is correct
16	Correct	5 ms	2688 KB	Output is correct
17	Correct	5 ms	2744 KB	Output is correct
18	Correct	5 ms	2688 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3044 KB	Output is correct
2	Correct	6 ms	2816 KB	Output is correct
3	Correct	14 ms	3600 KB	Output is correct
4	Correct	80 ms	7616 KB	Output is correct
5	Correct	54 ms	6652 KB	Output is correct
6	Correct	121 ms	10104 KB	Output is correct
7	Correct	6 ms	2816 KB	Output is correct
8	Correct	9 ms	3200 KB	Output is correct
9	Correct	13 ms	3756 KB	Output is correct
10	Correct	21 ms	4608 KB	Output is correct
11	Correct	82 ms	10108 KB	Output is correct
12	Correct	10 ms	3328 KB	Output is correct
13	Correct	7 ms	3072 KB	Output is correct
14	Correct	8 ms	2944 KB	Output is correct
15	Correct	9 ms	3200 KB	Output is correct
16	Correct	21 ms	3968 KB	Output is correct
17	Correct	107 ms	9688 KB	Output is correct
18	Correct	6 ms	2916 KB	Output is correct
19	Correct	6 ms	2944 KB	Output is correct
20	Correct	96 ms	10104 KB	Output is correct
21	Correct	7 ms	2944 KB	Output is correct
22	Correct	7 ms	2944 KB	Output is correct
23	Correct	9 ms	3244 KB	Output is correct
24	Correct	7 ms	3044 KB	Output is correct
25	Correct	9 ms	2944 KB	Output is correct
26	Correct	9 ms	2944 KB	Output is correct
27	Correct	9 ms	2944 KB	Output is correct
28	Correct	7 ms	2944 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	8876 KB	Output is correct
2	Correct	233 ms	12944 KB	Output is correct
3	Correct	190 ms	13128 KB	Output is correct
4	Correct	120 ms	8952 KB	Output is correct
5	Correct	47 ms	6908 KB	Output is correct
6	Correct	159 ms	11088 KB	Output is correct
7	Correct	108 ms	12632 KB	Output is correct
8	Correct	97 ms	12408 KB	Output is correct
9	Correct	83 ms	9208 KB	Output is correct
10	Correct	104 ms	10684 KB	Output is correct
11	Correct	265 ms	13008 KB	Output is correct
12	Correct	205 ms	12128 KB	Output is correct
13	Correct	141 ms	8016 KB	Output is correct
14	Correct	97 ms	10316 KB	Output is correct
15	Correct	74 ms	6868 KB	Output is correct
16	Correct	9 ms	4224 KB	Output is correct
17	Correct	8 ms	3968 KB	Output is correct
18	Correct	190 ms	12784 KB	Output is correct
19	Correct	213 ms	12764 KB	Output is correct
20	Correct	137 ms	8896 KB	Output is correct
21	Correct	56 ms	6868 KB	Output is correct
22	Correct	9 ms	4096 KB	Output is correct
23	Correct	47 ms	6200 KB	Output is correct
24	Correct	110 ms	9180 KB	Output is correct
25	Correct	89 ms	7544 KB	Output is correct
26	Correct	108 ms	7556 KB	Output is correct
27	Correct	272 ms	12196 KB	Output is correct
28	Correct	125 ms	7676 KB	Output is correct
29	Correct	97 ms	7780 KB	Output is correct
30	Correct	236 ms	12204 KB	Output is correct
31	Correct	122 ms	8508 KB	Output is correct
32	Correct	99 ms	8096 KB	Output is correct
33	Correct	107 ms	8132 KB	Output is correct
34	Correct	114 ms	8488 KB	Output is correct
35	Correct	95 ms	7584 KB	Output is correct
36	Correct	101 ms	7572 KB	Output is correct
37	Correct	105 ms	7724 KB	Output is correct