글 읽기 - 시간초과 왜날까요

jwpassion1 3년 전 0

시간복잡도가 O(V + E)라는데 제 생각에는 정점 4백만에 간선 8백만이 최대 같은데요

+ 덱을 스택으로 바꾸고 백터 하나 지우니 해결됬네요 뭐지

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;

vector<vector<int>> scc, graph;
vector<int> discover, sccnum;
deque<pair<int, int>> sta;
int dis = 1, sc = 0;

int dfs(int a){
	discover[a] = dis++;
	int ret = discover[a];
	sta.push_back({ discover[a], a });
	for (const int& i : graph[a]){
		if (!discover[i]) ret = min(ret, dfs(i));
		else if (sccnum[i] == -1) ret = min(ret, discover[i]);
	}
	if (ret == discover[a]){
		scc.resize(sc + 1);
		while (1){
			pair<int, int> b = sta.back();
			sta.pop_back();
			scc[sc].push_back(b.second);
			sccnum[b.second] = sc;
			if (b.first == discover[a]) break;
		}
		sc++;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, k, a, b, w;
	cin >> n >> m >> k;
	graph.resize(n * 4);
	discover.resize(n * 4);
	sccnum.resize(n * 4, -1);
	vector<vector<int>> contury(k);

	for (int i = 0; i < m; i++){
		cin >> a >> b;
		graph[--a + n * 2].push_back(--b);
		graph[b + n * 2].push_back(a);
	}

	for (int i = 0; i < k; i++){
		cin >> w;
		contury[i].resize(w);
		for (int j = 0; j < w; j++){
			cin >> contury[i][j];
			contury[i][j]--;
		}
		for (int j = 0; j < w - 1; j++){
			graph[contury[i][j]].push_back(contury[i][j] + n);
			graph[contury[i][j] + n * 3].push_back(contury[i][j] + n * 2);
			graph[contury[i][j] + n].push_back(contury[i][j + 1] + n);
			graph[contury[i][j + 1] + n * 3].push_back(contury[i][j] + n * 3);
			graph[contury[i][j] + n].push_back(contury[i][j + 1] + n * 2);
			graph[contury[i][j + 1]].push_back(contury[i][j] + n * 3);
		}
	}

	for (int i = 0; i < n * 4; i++){
		if (!discover[i]) dfs(i);
	}

	for (int i = 0; i < n * 2; i++){
		if (sccnum[i] == sccnum[i + n * 2]){
			cout << "NIE";
			return 0;
		}
	}

	cout << "TAK\n";
	for (int i = 0; i < k; i++){
		for (const int& j : contury[i]){
			if (sccnum[j] < sccnum[j + n * 2]){
				cout << j + 1 << ' ';
				break;
			}
		}
	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 왜날까요

jwpassion1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말