제출 #203611

#제출 시각아이디문제언어결과실행 시간메모리
203611ics0503Meetings (JOI19_meetings)C++17
0 / 100
7 ms760 KiB
#include "meetings.h" #include<vector> #include<algorithm> using namespace std; int is_in[2121], P[2121], W[2121][2121]; struct xy { int x, y; }; bool sort_y(xy a, xy b) { if (a.y != b.y)return a.y < b.y; return a.x < b.x; } vector<xy>edge[2121]; int C[2121], nown, mx, cent; void dfs(int w, int bef) { C[w] = 1; for (xy E : edge[w]) if (!E.y && E.x != bef) { dfs(E.x, w); C[w] += C[E.x]; } if (C[w] <= nown / 2 && mx < C[w]) mx = C[w], cent = w; } void connect(int p, int c, int who) { int x = Query(p, c, who); if (x == p)P[c] = P[who] = p; else if (x == c)P[c] = p, P[who] = c; else if (x == who)P[c] = who, P[who] = p; else is_in[x] = 1, P[c] = P[who] = x, P[x] = p; } void disconnect(int a, int b) { edge[a][W[a][b]].y = edge[b][W[b][a]].y = 1; } void Solve(int N) { connect(0, 1, 2); is_in[0] = is_in[1] = is_in[2] = 1; for (int now = 3; now < N; now++) { if (is_in[now])continue; nown = 1; for (int i = 1; i < N; i++) { if (is_in[i]) { W[P[i]][i] = edge[P[i]].size(); edge[P[i]].push_back({ i,0 }); W[i][P[i]] = edge[i].size(); edge[i].push_back({ P[i],0 }); nown++; } } int root = 0; while (1) { mx = cent = 0; dfs(root, -1); if (C[root] == 1) { P[now] = root; break; } vector<xy>L; int cnt = 0; for (xy E : edge[cent]) if (!E.y) L.push_back({ E.x, C[E.x] - (C[E.x] < C[cent] ? 0 : C[cent]) }); sort(L.begin(), L.end(), sort_y); if (L.size() == 1) { int who = L[0].x, p, c; if (C[who] > C[cent]) p = who, c = cent; else p = cent, c = who; connect(p, c, now); break; } else { int ck = 0; root = cent; for (int i = 0; i < L.size(); i += 2) { int a = L[i].x, b = L[i + 1].x; int x = Query(a, b, now); if (x == cent) disconnect(a, cent), disconnect(b, cent); else { if (x == a) disconnect(a, cent), root = a; else if (x == b) disconnect(b, cent), root = b; else { int y = Query(a, x, cent); ck = 1; if (y == x) { if (P[a] == cent) { P[a] = P[now] = x; P[x] = cent; is_in[x] = 1; } else { P[cent] = P[now] = x; P[x] = a; is_in[x] = 1; } } else { if (P[b] == cent) { P[b] = P[now] = x; P[x] = cent; is_in[x] = 1; } else { P[cent] = P[now] = x; P[x] = b; is_in[x] = 1; } } } break; } } if (ck) break; } } is_in[now] = 1; for (int i = 0; i < N; i++)edge[i].clear(); } for (int i = 1; i < N; i++) { if(i<P[i]) Bridge(i, P[i]); else Bridge(P[i], i); } }

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < L.size(); i += 2) {
                     ~~^~~~~~~~~~
meetings.cpp:43:21: warning: unused variable 'cnt' [-Wunused-variable]
    vector<xy>L; int cnt = 0;
                     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...