14615 Defend the CTP!!!

 

 

 

1. bfs로 시도했다 -> 시간초과

2. 한번 확인한 경우는 값을 저장해놓으면 빨라지지 않을까? -> 시간초과

3. cin으로 빠른 입출력을 사용하면? -> 시간초과

 

3진 시간초과로 다음 문제로 넘어갔다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int n, m;
vector<vector<int>> adj(100005);
vector<int> dp(100005, -1);

bool move(int start, int end) {
    vector<bool> visited(100005);
    
    queue<int> Q;
    Q.push(start);
    visited[start] = true;
    
    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        
        if (curr == end)
            return true;
        for (int next : adj[curr])
        {
            if (!visited[next])
            {
                visited[next] = true;
                Q.push(next);
            }
        }
    }
    
    return false;
}

void solve() {
    int bomb;
    cin >> bomb;
    
    bool check = dp[bomb] != -1 ? dp[bomb] : move(1, bomb) && move(bomb, n);
    
    if (check) {
        cout << "Defend the CTP\n";
        dp[bomb] = 1;
        return;
    }
    cout << "Destroyed the CTP\n";
    dp[bomb] = 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
    }
    
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    
    return 0;
}

 

알고보니!!! 

 

1에서 출발해서 갈 수 있는 곳을 체크하고 x에서 출발해서 n으로 갈 수 있는 곳을 체크한 다음 둘 다 true인 곳을 구하면 된다.

그런데 x에서 출발해서 n으로 갈 수 있는 곳을 체크하는 건 어려우므로

역방향으로 n에서 갈 수 있는 곳을 체크한다(!!!!!!!!!) 이렇게 풀 수 있구나. 

 

그런데 내가 푼 건 n * m * bfs여서 시간 초과가 났다. 이유가 있었군

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int n, m;
vector<int> adj[100005];
vector<int> rev[100005];
bool dist1[100005], distN[100005];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        rev[y].push_back(x);
    }
    
    // dist1
    queue<int> Q;
    Q.push(1);
    dist1[1] = true;
    
    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        
        for (int next : adj[curr])
        {
            if (dist1[next])
                continue;
            
            dist1[next] = true;
            Q.push(next);
        }
    }
    
    // distN
    Q.push(n);
    distN[n] = true;
    
    while (!Q.empty())
    {
        int curr = Q.front();
        Q.pop();
        
        for (int next : rev[curr])
        {
            if (distN[next])
                continue;
            
            distN[next] = true;
            Q.push(next);
        }
    }
    
    int t;
    cin >> t;
    
    for (int i = 0; i < t; i++) {
		int c;
		cin >> c;

		if (dist1[c] && distN[c])
			cout << "Defend the CTP\n";
		else
			cout << "Destroyed the CTP\n";
    }
    
    return 0;
}