Gym-101873D-Pants On Fire（闭包）

原题链接：2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)

Pants On Fire

Donald and Mike are the leaders of the free world and haven’t yet (after half a year) managed to start a nuclear war. It is so great! It is so tremendous!

Despite the great and best success of Donald’s Administration, there are still a few things he likes to complain about.

The Mexican government is much smarter, much sharper, and much more cunning. And they send all these bad hombres over because they don’t want to pay for them. They don’t want to take care of them.

Donald J. Trump, First Republican Presidential Debate, August 6, 2015

He also frequently compares Mexicans to other bad people (like Germans, since they are exporting so many expensive cars to the US). Due to the tremendous amount of statements he has made (mostly containing less than 140 characters ...) the “Fake-News” New York Telegraph (NYT) has to put in a lot of effort to clarify and comment on all the statements of Donald. To check a statement, they have a list of facts they deem to be true and classify Donald’s statements into three groups: real facts (which are logical conclusions from their list of true facts), exaggerations (which do not follow, but are still consistent with the papers list of facts), and alternative facts (which contradict the knowledge of the newspaper).

They have asked you to write a program helping them to classify all of Donald’s statements – after all it is hard for a journalist to go through them all and check them all, right?

Input

The input consists of:

- one line containing two integers n and m, where
  - n (1 ≤ n ≤ 200) is the number of facts deemed true by the NYT;
  - m (1 ≤ m ≤ 200) is the number of statements uttered by the Donald.
- n lines each containing a statement deemed true by the NYT.
- m lines each containing a statement uttered by the Donald.

All statements are of the form a are worse than b, for some strings a and b, stating that a is (strictly) worse than b. The strings a and b are never identical. Both a and b are of length between 1 and 30 characters and contain only lowercase and uppercase letters of the English alphabet.

Note that Donald’s statements may contain countries that the NYT does not know about. You may assume that worseness is transitive and that the first n lines do not contain any contradictory statement. Interestingly, Donald’s press secretary (Grumpy Sean) has managed to convince him not to make up countries when tweeting, thus the input mentions at most 193 different countries.

Output

For every of the m statements of Donald output one line containing

Fact if the statement is true given the n facts of the NYT
Alternative Fact if the inversion of the statement is true given the n facts of the NYT
Pants on Fire if the statement does not follow, but neither does its inverse.

Sample Input 1

4 5

Mexicans are worse than Americans

Russians are worse than Mexicans

NorthKoreans are worse than Germans

Canadians are worse than Americans

Russians are worse than Americans

Germans are worse than NorthKoreans

NorthKoreans are worse than Mexicans

NorthKoreans are worse than French

Mexicans are worse than Canadians

Sample Output 1

Fact

Alternative Fact

Pants on Fire

求个传递闭包就能AC，拷贝到了东庆巨巨的代码，顺便学了点用map把串转化成下标；话说这个闭包写的真漂亮

#include <bits/stdc++.h>
using namespace std;

map <string, int> data;

const int MAX = 500;
int tot;

int get( string str )
{
    if( data.count(str) ) return data[str];
    tot = data.size();
    data[str] = ++tot;
    return data[str];
}

int edge[MAX][MAX];

int main()
{
    int n, m;
    cin >> n >> m;
    while( n-- )
    {
        int u, v;
        string str;
        cin >> str;
        u = get(str);
        cin >> str;
        cin >> str;
        cin >> str;
        cin >> str;
        v = get(str);
        edge[u][v] = 1;
    }
    for( int c = 1; c <= tot; c++ )
        for( int a = 1; a <= tot; a++ )
            for( int b = 1; b <= tot; b++ )
                edge[a][b] |= edge[a][c] && edge[c][b];
    while( m-- )
    {
        int u, v;
        string str;
        cin >> str;
        u = get(str);
        cin >> str;
        cin >> str;
        cin >> str;
        cin >> str;
        v = get(str);

        if( edge[u][v] ) printf("Fact\n");
        else if( edge[v][u] ) printf("Alternative Fact\n");
        else printf("Pants on Fire\n");
    }
    return 0;
}

Gym-101873D-Pants On Fire（闭包）

Pants On Fire

推荐阅读