Submission #524576


Source Code Expand

Copy
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>

using namespace std;
static const double EPS = 1e-9;
template<class T> bool INRANGE(T x,T a,T b){return a<=x&&x<=b;}
template<class T> void amin(T &a,T v){if(a>v) a=v;}
template<class T> void amax(T &a,T v){if(a<v) a=v;}
int ROUND(double x) { return (int)(x+0.5); }
bool ISINT(double x) { return fabs(ROUND(x)-x)<=EPS; }
bool ISEQUAL(double x,double y) { return fabs(x-y)<=EPS*max(1.0,max(fabs(x),fabs(y))); }
double SQSUM(double x,double y) { return x*x+y*y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef long long ll;
typedef unsigned long long ull;


#if 1

class BipartiteMatching
{
public:
	BipartiteMatching(int v) : V(v) 
	{
		init();
	}

	void init()
	{
		G.clear();
		G.resize(V);
		match.clear();
		match.resize(V);
		used.clear();
		used.resize(V);
	}

	void add_edge(int u, int v)
	{
		G[u].push_back(v);
		G[v].push_back(u);
	}

	int run()
	{
		int res=0;
		fill(match.begin(),match.end(),-1);
		for(int v=0;v<V;v++)
		{
			if(match[v]<0)
			{
				fill(used.begin(),used.end(),false);
				if(dfs(v))
				{
					res++;
				}
			}
		}

		return res;
	}

private:
	const int V;
	vector < vector <int> > G;
	vector <int> match;
	vector <bool> used;


	bool dfs(int v)
	{
		used[v]=true;
		for(int i=0;i<SZ(G[v]);i++)
		{
			int u=G[v][i];
			int w=match[u];
			if(w<0||!used[w]&&dfs(w))
			{
				match[v]=u;
				match[u]=v;
				return true;
			}
		}
		return false;
	}
};

int main()
{
	int N;
	scanf("%d ",&N);

	N = 2*N+1;

	vector <int> bx(N);
	vector <int> by(N);
	for (int i = 0; i < N; ++i)
	{
		scanf("%d %d ",&bx[i], &by[i]);
	}

	for (int i = 0; i < N; ++i)
	{
		vector <int> x;
		vector <int> y;
		for (int k = 0; k < N; ++k)
		{
			if(i!=k)
			{
				x.push_back(bx[k]);
				y.push_back(by[k]);
			}
		}

		const int S = SZ(x);
		BipartiteMatching* bm = new BipartiteMatching(S*2);

		for (int a = 0; a < S; ++a)
		{
			for (int b = 0; b < S; ++b)
			{
				if(a!=b && (x[a]==x[b] || y[a]==y[b]))
				{
					bm->add_edge(a,b+S);
				}
			}
		}

		int a = bm->run();
		if(a==S)
		{
			printf("OK\n");
		}
		else
		{
			printf("NG\n");
		}






		delete bm;
	}

	return 0;
}

#elif 1

vector < vector <pair <int, int> > > edgelist; // 隣接リスト
vector <bool> visited;			// 訪れたかどうか。双方向隣接リストになってるので、木を走査するときに、子→親に逆流するのを防がないといけないので必要。このフラグはnum_patternsとは別に必要。
vector <int> sumxor;

// vをルートとする部分木
void dfs(int v, int sum)
{
	if(!visited[v]) {
		visited[v] = true;
		sumxor[v] = sum;
	}

	for (int i = 0; i < SZ(edgelist[v]); i++)
	{
		int next_v = edgelist[v][i].first;
		if(!visited[next_v]) // 子だけ見るように
		{
			dfs(next_v, sum ^ edgelist[v][i].second);
		}
	}
}


int main()
{
	int N,X;
	scanf("%d %d ",&N, &X);

	edgelist.resize(N);
	visited.resize(N);
	sumxor.resize(N);

	for (int i = 0; i < N-1; ++i)
	{
		int x,y,c;
		scanf("%d %d %d ",&x, &y, &c);
		x--;
		y--;
		edgelist[x].push_back(make_pair(y,c));
		edgelist[y].push_back(make_pair(x,c));
	}

	dfs(0,0);

	map <int, int> mp;
	for (const auto& a : sumxor)
	{
		mp[a]++;
	}

	ll ans = 0;
	
	for (const auto& a : mp)
	{
		const map <int, int>::iterator it = mp.find(a.first ^ X);
		if(it!=mp.end())
		{
			if((a.first ^ X) == a.first)
			{
				ans += (ll)a.second * (ll)(it->second-1);
			}
			else
			{
				ans += (ll)a.second * (ll)it->second;
			}
		}
	}

	ans /= 2;


	cout << ans << endl;

	return 0;
}


#elif 1

int main()
{
	int N,M;
	scanf("%d %d ",&N, &M);

	vector <int> start(M), end(M);
	for(int i=0;i<M;i++)
	{
		scanf("%d %d ",&start[i], &end[i]);
	}

	vector <int> rooms(300005);
	for(int i=0;i<M;i++)
	{
		rooms[start[i]]++;
		rooms[end[i]+1]--;
	}

	for (int i = 0; i <= N; ++i)
	{
		rooms[i+1] += rooms[i];
	}

	vector <int> saboren;
	for (int i = 0; i <= N; ++i)
	{
		if(rooms[i]==1)
		{
			saboren.push_back(i);
		}
	}

	vector <int> ans;
	saboren.push_back(BIG);
	for(int i=0;i<M;i++)
	{
		int lb = *lower_bound(saboren.begin(),saboren.end(),start[i]);
		if(lb>end[i])
		{
			ans.push_back(i+1);
		}
	}

	printf("%d\n",SZ(ans));
	for (int i = 0; i < SZ(ans); ++i)
	{
		printf("%d\n",ans[i]);
	}

	return 0;

}


#else

int main()
{
	vector <string> vs;
	string s;
	while( cin >> s )
	{
		vs.push_back(s);
	}

	for (int i = 0; i < SZ(vs); ++i)
	{
		if(vs[i]=="Left")
		{
			printf("<");
		}
		else if (vs[i]=="Right")
		{
			printf(">");
		}
		else if (vs[i]=="AtCoder")
		{
			printf("A");
		}

		if(i<SZ(vs)-1)
		{
			printf(" ");
		}
	}
	printf("\n");

	return 0;

}


#endif

Submission Info

Submission Time
Task D - みんな仲良し高橋君
User shindannin
Language C++11 (GCC 4.9.2)
Score 0
Code Size 5505 Byte
Status
Exec Time 3090 ms
Memory 536716 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:119:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d ",&N);
                 ^
./Main.cpp:127:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d ",&bx[i], &by[i]);
                                 ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0.txt, example_1.txt, example_2.txt
Subtask1 0 / 30 bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_bubun_0.txt, random_bubun_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_bubun_0.txt, square_bubun_1.txt
All 0 / 70 bone_0.txt, bone_1.txt, bone_2.txt, bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, example_0.txt, example_1.txt, example_2.txt, handmade_0.txt, handmade_1.txt, handmade_2.txt, handmade_3.txt, komakai_0.txt, komakai_1.txt, komakai_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_0.txt, random_1.txt, random_bubun_0.txt, random_bubun_1.txt, renket_0.txt, renket_1.txt, smallrand_0.txt, smallrand_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_0.txt, square_1.txt, square_bubun_0.txt, square_bubun_1.txt, supersmall_0.txt, supersmall_1.txt, threeren_0.txt, threeren_1.txt, treebase_0.txt, treebase_1.txt, treebase_2.txt, example_0.txt, example_1.txt, example_2.txt
Case Name Status Exec Time Memory
bone_0.txt 3082 ms 410756 KB
bone_1.txt 3084 ms 407316 KB
bone_2.txt 3084 ms 413960 KB
bone_bubun_0.txt 3079 ms 403208 KB
bone_bubun_1.txt 3073 ms 341148 KB
bone_bubun_2.txt 3090 ms 536716 KB
example_0.txt 25 ms 928 KB
example_1.txt 25 ms 732 KB
example_2.txt 23 ms 928 KB
handmade_0.txt 25 ms 928 KB
handmade_1.txt 23 ms 796 KB
handmade_2.txt 23 ms 928 KB
handmade_3.txt 23 ms 804 KB
komakai_0.txt 3036 ms 17196 KB
komakai_1.txt 3036 ms 16400 KB
komakai_2.txt 3035 ms 17292 KB
komakai_bubun_0.txt 3037 ms 15500 KB
komakai_bubun_1.txt 3035 ms 15636 KB
komakai_bubun_2.txt 3036 ms 15628 KB
maxrand_0.txt 3035 ms 15504 KB
maxrand_1.txt 3036 ms 15620 KB
maxrand_bubun_0.txt 3036 ms 15748 KB
maxrand_bubun_1.txt 3035 ms 15760 KB
random_0.txt 3034 ms 1692 KB
random_1.txt 3034 ms 10000 KB
random_bubun_0.txt 3033 ms 2244 KB
random_bubun_1.txt 3034 ms 7328 KB
renket_0.txt 3034 ms 16660 KB
renket_1.txt 3034 ms 16660 KB
smallrand_0.txt 70 ms 924 KB
smallrand_1.txt 68 ms 800 KB
smallrand_bubun_0.txt 27 ms 796 KB
smallrand_bubun_1.txt 24 ms 756 KB
smallrand_bubun_2.txt 24 ms 800 KB
square_0.txt 3041 ms 65040 KB
square_1.txt 3039 ms 65292 KB
square_bubun_0.txt 3041 ms 66188 KB
square_bubun_1.txt 3043 ms 71312 KB
supersmall_0.txt 26 ms 796 KB
supersmall_1.txt 26 ms 920 KB
threeren_0.txt 3034 ms 16300 KB
threeren_1.txt 3036 ms 16264 KB
treebase_0.txt 3036 ms 15124 KB
treebase_1.txt 3033 ms 8348 KB
treebase_2.txt 3035 ms 12696 KB