Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么G++超时C++就过了400ms(附代码)求dalao给看看

Posted by ICLiuLi at 2017-08-04 20:57:59 on Problem 1386 and last updated at 2017-08-04 20:59:59
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
string x1;
int f[26], num, cntr[26], cntc[26], ji1, ji2, ji3, t, x, y;
int find(int a){ return f[a] == a ? f[a] : f[a] = find(f[a]); };
void he(int a, int b){
	int fa = find(a), fb = find(b);
	if (fa != fb)
		f[fa] = fb;
}
int main(){
	scanf("%d", &t);
	while (t--){
		ji1 = 0, ji2 = 0, ji3 = 0;
		scanf("%d", &num);
		for (int a = 0; a < 26; a++)
			f[a] = a, cntr[a] = 0, cntc[a] = 0;
		while (num--){
			cin >> x1;
			x = x1[0] - 'a', y = x1[x1.size() - 1] - 'a';
			cntr[x]++, cntc[y]++;
			he(x, y);
		}
		for (int a = 0; a < 26; a++)
		if (a == find(a) && (cntr[a] || cntc[a]))
			ji1++;
		if (ji1>1){
			printf("The door cannot be opened.\n");
			continue;
		}
		ji1 = 0, ji2 = 0, ji3 = 0;
		for (int a = 0; a < 26; a++)
		if (cntr[a] == cntc[a] + 1)
			ji1++;
		else if (cntc[a] == cntr[a] + 1)
			ji2++;
		else if (cntc[a] != cntr[a])
			ji3++;
		if (!ji3 && ((!ji1 && !ji2) || (ji1 == 1 && ji2 == 1)))
			printf("Ordering is possible.\n");
		else
			printf("The door cannot be opened.\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator