| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么G++超时C++就过了400ms(附代码)求dalao给看看#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator