제출 #249466

#제출 시각아이디문제언어결과실행 시간메모리
249466cheehengMeetings (JOI19_meetings)C++14
29 / 100
3075 ms9104 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; int lca[2005][2005]; vector<int> AdjList[2005]; vector<int> toposort; bool visited[2005]; void dfs(int u){ if(visited[u]){return;} visited[u] = true; //printf("dfs(%d)\n", u); for(int v: AdjList[u]){ dfs(v); } toposort.push_back(u); } void Solve(int N) { lca[0][0] = 0; for(int i = 1; i < N; i ++){ lca[0][i] = 0; lca[i][0] = 0; } for(int i = 1; i < N; i ++){ lca[i][i] = i; for(int j = i+1; j < N; j ++){ lca[i][j] = Query(0, i, j); lca[j][i] = lca[i][j]; } } for(int i = 0; i < N; i ++){ for(int j = 0; j < N; j ++){ if(i == j){continue;} if(lca[i][j] == i){ AdjList[i].push_back(j); } } } dfs(0); reverse(toposort.begin(), toposort.end()); /*printf("Toposort: "); for(int i = 0; i < N; i ++){ printf("%d ", toposort[i]); } printf("\n");*/ for(int i = N-1; i >= 1; i --){ for(int j = i-1; j >= 0; j --){ int u = toposort[i]; int v = toposort[j]; if(lca[u][v] == v){ Bridge(min(u, v), max(u, v)); break; } } } return; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...