I finally figured out how to get past the TLE. Unfortunately now I have WA on PC and RTE on UVA. Can anybody give out some test cases? I did a simple one like this:
Code: Select all
1
12 16
Erdos, P., C, C: asdf
Erdos, P., B, B: asdf
Erdos, P., A, A: asdfa
B, B, G, G: asdf
A, A, H, H: asdf
H, H, I, I: asdf
I, I, J, J, K, K: asdf
J, J, L, L: asdf
L, L, F, F: asdf
C, C, F, F: aadsf
F, F, D, D, E, E: asdf
M, M, N, N, O, O: asdf
Erdos, P.
A, A
B, B
C, C
D, D
E, E
F, F
G, G
H, H
I, I
J, J
K, K
L, L
M, M
N, N
O, O
which gives the output of:
Code: Select all
Scenario 1
Erdos, P. 0
A, A 1
B, B 1
C, C 1
D, D 3
E, E 3
F, F 2
G, G 2
H, H 2
I, I 3
J, J 4
K, K 4
L, L 3
M, M infinity
N, N infinity
O, O infinity
It also passes the sample input, and double sample input. I'm really stumped on why this is incorrect. Thanks for any help! (code following)
Note: I have tried removing all white space (/t, /r, ' ', & '.') like it says earlier in the thread, and it still doesn't work. So I think I must be doing something different wrong. :\
Code: Select all
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <queue>
//max links 500
//max person names length 100
//max input line length 10000
//max names 5000
std::vector<bool> T;
std::vector<int> mem;
std::vector<std::vector<bool> > matrix;
void solve(int from);
std::string removeWhite(std::string str);
int main(){
int cases;
int paper_count;
int author_count;
int count;
int C;
int B;
std::string line;
std::string temp;
char A[1000];
char *P;
std::vector<std::vector<std::string> > papers;
std::vector<std::string> S;
std::map<std::string, int> authors;
std::map<std::string, int>::iterator iter;
std::cin >> cases;
for(int i = 0; i < cases; i++){
papers.resize(0);
matrix.resize(0);
T.resize(0);
authors.erase(authors.begin(), authors.end());
std::cin >> paper_count >> author_count;
papers.resize(paper_count);
count = 0;
std::getline(std::cin, line); //garbage - whitespace
for(int j = 0; j < paper_count; j++){
line = "";
std::getline(std::cin, line);
strcpy(A, line.c_str());
P = strtok(&A[0], ",");
while(P != NULL){
temp = std::string(P);
papers[j].push_back(temp);
P = strtok(NULL, ",");
}
line = papers[j][papers[j].size()-1];
papers[j].pop_back();
strcpy(A, line.c_str());
P = strtok(&A[0], ":");
temp = std::string(P);
papers[j].push_back(temp);
while(P != NULL){
P = strtok(NULL, ":");
}
S.resize(0);
for(int p = 0; p < papers[j].size(); p+=2){
S.push_back(papers[j][p]+ "," + papers[j][p+1]);
}
papers[j] = S;
//remove leading spaces
for(int o = 0; o < papers[j].size(); o++){
if(papers[j][o][0] == ' '){
papers[j][o] = papers[j][o].substr(1, papers[j][o].length()-1);
}
authors[papers[j][o]] = count++;
}
}
//init matrix
T.resize(count, false);
matrix.resize(count, T);
//adjacency matrix
for(int pedro_for_president = 0; pedro_for_president < papers.size(); pedro_for_president++){
for(int w = 0; w < papers[pedro_for_president].size(); w++){
C = authors[papers[pedro_for_president][w]];
for(int q = 0; q < papers[pedro_for_president].size(); q++){
B = authors[papers[pedro_for_president][q]];
if(C != B){
matrix[C][B] = true;
}
}
}
}
std::cout << "Scenario " << i+1 << "\n";
mem.resize(0);
mem.resize(matrix.size(), -1);
solve(authors["Erdos, P."]);
for(int k = 0; k < author_count; k++){
std::getline(std::cin, line);
//output
std::cout << line << " ";
if(mem[authors[line]] == -1){
std::cout << "infinity";
}
else{
std::cout << mem[authors[line]];
}
std::cout << "\n";
}
}
}
void solve(int from){
std::vector<bool> visited;
std::queue<int> Q;
int jumps = 0;
int to_pop;
visited.resize(0);
visited.resize(matrix.size(), false);
visited[from] = true;
Q.push(from);
while(Q.empty() == false){
to_pop = Q.size();
for(int j = 0; j < to_pop; j++){
mem[Q.front()] = jumps;
for(int i = 0; i < matrix.size(); i++){
if((matrix[Q.front()][i]) &&
(visited[i] == false)){
visited[i] = true;
Q.push(i);
}
}
Q.pop();
}
jumps++;
}
}
std::string removeWhite(std::string str){
}
[/code][/list]
