brandonjo   3년 전

코딩을 열심히 공부하고 있고 재미를 느껴 백준을 연마하고 있는 초등학생입니다. 

친구(honda0422)가 제 계정에 들어가 루비 문제를 다른 사람 코드 베껴서 채점 받고 튀었어요.문제 풀기 전으로 상태로 되돌려주세요.ㅠㅠ 도와주세요...(ㄴ외곽순환도로)

maxgt222   3년 전

님 저도 초등학생인데 저도 루비 문제 풀었는데 제 코드 드릴까요??

ㄴ외곽순환도로 

추신: 원래 다이아 문제 안 풀고 루비 문제 풀면 정지 먹어요 

maxgt222   3년 전

//외곽순환도로 코드 ^^ #include #include #include #include #include #include #include using namespace std; using lint = long long; using pi = pair; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() const int MAXN = 200005; struct query{ int s, e, idx; bool operator<(const query &q)const{ return s < q.s; } }; vector gph[MAXN]; vector tr[MAXN]; vector dfn; int label[MAXN], vis[MAXN]; int sz[MAXN], msz[MAXN]; lint ans[250005]; void dfs(int x, int p){ dfn.push_back(x); sz[x] = 1; msz[x] = 0; for(auto &y : tr[x]){ if(y != p && !vis[y]){ dfs(y, x); sz[x] += sz[y]; msz[x] = max(msz[x], sz[y]); } } } int get_center(int x){ dfs(x, -1); pi ret(1e9, -1); for(auto &v : dfn){ int val = max(msz[v], sz(dfn) - sz[v]); ret = min(ret, pi(val, v)); } return ret.second; } void fill_label(int x, int p, int v){ label[x] = v; for(auto &y : tr[x]){ if(y != p && !vis[y]) fill_label(y, x, v); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; { vector pidx(n + 1); iota(all(pidx), 0); vector needClean(n + 1); int cnt = n; for(int i = 2; i <= n; i++){ lint p, w; cin >> p >> w; if(needClean[p]){ cnt++; gph[cnt].emplace_back(0, pidx[p]); gph[pidx[p]].emplace_back(0, cnt); tr[pidx[p]].push_back(cnt); tr[cnt].push_back(pidx[p]); pidx[p] = cnt; needClean[p] = 0; } gph[pidx[p]].emplace_back(w, i); gph[i].emplace_back(w, pidx[p]); tr[pidx[p]].push_back(i); tr[i].push_back(pidx[p]); needClean[p] = 1; } vector v; for(int i = 1; i <= n; i++){ if(sz(gph[i]) == 1) v.push_back(i); } for(int i = 0; i < sz(v); i++){ int x = v[i], y = v[(i + 1) % sz(v)]; lint w; cin >> w; gph[x].emplace_back(w, y); gph[y].emplace_back(w, x); } n = cnt; } int q; cin >> q; vector queries; memset(ans, 0x3f, sizeof(ans)); for(int i = 0; i < q; i++){ int s, e; cin >> s >> e; queries.push_back({s, e, i}); } queue>> que; que.emplace(1, queries); vector dist(n + 1, 1e18); while(sz(que)){ int x = que.front().first; auto queries = que.front().second; que.pop(); dfn.clear(); x = get_center(x); int cnt = 0; for(auto &y : tr[x]){ if(!vis[y]){ fill_label(y, x, ++cnt); } } label[x] = -1; vector todo = {x}; for(auto &v : dfn){ for(auto &[_, w] : gph[v]){ if(label[v] > 0 && label[w] > 0 && label[v] < label[w]){ todo.push_back(v); } } } assert(sz(todo) <= 4); for(auto &v : todo){ for(auto &w : dfn) dist[w] = 1e18; priority_queue, greater > pq; auto enq = [&](int x, lint v){ if(label[x] && dist[x] > v){ dist[x] = v; pq.emplace(v, x); } }; enq(v, 0); while(sz(pq)){ auto x = pq.top(); pq.pop(); if(dist[x.second] != x.first) continue; for(auto &y : gph[x.second]){ enq(y.second, y.first + x.first); } } for(auto &q : queries){ ans[q.idx] = min(ans[q.idx], dist[q.s] + dist[q.e]); } } vector> vect(cnt); for(auto &q : queries){ if(label[q.s] <= 0 || label[q.e] <= 0 || label[q.s] != label[q.e]) continue; vect[label[q.s] - 1].push_back(q); } vis[x] = 1; int tcnt = 0; for(auto &y : tr[x]){ if(!vis[y]){ que.emplace(y, vect[tcnt++]); } } for(auto &z : dfn){ label[z] = 0; } } for(int i = 0; i < q; i++) cout << ans[i] << "\n"; }

maxgt222   3년 전

ㅋ

maxgt222   3년 전

아님 부계를 파서 하면 되지 않을까요>>>

maxgt222   3년 전

어 잠만 님 대치초등학교 ㅇ에요>???

maxgt222   3년 전

저도 대치초등학교인데 몇학년 몇반이에요?

maxgt222   3년 전

메롱메롱메롱메롱메롱메롱

ufshg   3년 전

베낀건 풀었다고 하는게 아닙니다.

정지도 되셨네요.

brandonjo   3년 전

베낀건 아닌데용?

ㅋㅋㄹ

brandonjo   3년 전

어쩔티비 ㅋㅋㄹㅃㅃ

brandonjo   3년 전

어쩔 ㅋㅋㄹㅃㅃ

brandonjo   3년 전

그리고 ufshg님 maxgt222는 부계인데요?

brandonjo   3년 전

본계 따로 있음 님보다 높음                           ㅎㅎㅎㅎㅎㅎㅎ (의 반대) (사실 플래티넘 5임) ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

brandonjo   3년 전

ugshg님 정말 죄송합니다. 저의 동생이 실례를 범했군요 사과드리겠습니다.

ㅠ

qwerasdfzxcl   3년 전

귀엽다

brandonjo   3년 전

저 학교에서 딴짓 하는중

ㅋ

ufshg   3년 전

네,,,그러세요

maxgt222   3년 전

엇.

maxgt222   3년 전

우리 축구팀 15:0으로 이겼다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

대치초 vs 신구초

우승은 대치초!

tuna130411   1년 전

죄다 정지먹으셨네... 문제는 정직하게 풉시다

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