제출 #93615

#제출 시각아이디문제언어결과실행 시간메모리
93615adminCity Mapping (NOI18_citymapping)C++17
컴파일 에러
0 ms0 KiB
#include "citymapping.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll LINF = 0x3f3f3f3f3f3f3f3f; vector<pll> lis; ll di[1010][1010]; vector<pll> ttis[1010]; int par[1010]; ll calc(int u, int v) { if (di[u][v]) return di[u][v]; if (u==v) return 0; ll d = get_distance(u,v); di[u][v] = di[v][u] = d; return d; } int head, q; int dir[1010][1010]; void add(int u, int v, int A[], int B[], int W[]) { A[q] = u; B[q] = v; W[q] = calc(head,v)-calc(head,u); par[v] = u; ttis[u].push_back(pll(W[q],v)); int p = v; while(p!=head) { int pp = par[p]; for (int i=0;i<ttis[pp].size();i++) if (ttis[pp][i].second==p) { dir[pp][v] = i; break; } p = pp; } q++; } int D[1010], E[1010]; void dfs(int here) { for (pll &tmp : ttis[here]) { dfs(tmp.second); } if (ttis[here].empty()) { D[here] = 0; E[here] = here; return; } if (ttis[here].size()==1) { D[here]=D[ttis[here][0].second]; E[here]=E[ttis[here][0].second]; return; } int t = (D[ttis[here][0].second]>D[ttis[here][1].second]?0:1); D[here]=max(D[ttis[here][t].second]-1,D[ttis[here][1-t].second]); E[here]=E[ttis[here][t].second]; } void find_roads(int N, int Q, int A[], int B[], int W[]) { memset(par,-1,sizeof(par)); int i, j; ll maxi = 0; for (i=1;i<n;i++) { if (maxi<calc(0,i)) { maxi=calc(0,i); head=i; } } //printf("\n%d\n",head); vector<pll> pis; for (i=0;i<n;i++) { //if (calc(head,i)+calc(0,i)==calc(0,head)) { // pis.push_back(pll(calc(i,head),i)); //} //else lis.push_back(pll(calc(i,head),i)); } //sort(pis.begin(),pis.end()); //for (j=1;j<pis.size();j++) { // add(pis[j-1].second,pis[j].second); //} sort(lis.begin(),lis.end()); add(lis[0].second,lis[1].second,A,B,W); for (j=2;j<lis.size();j++) { dfs(lis[1].second); int idx = lis[j].second; ll mini = LINF; int p = lis[1].second; while(!ttis[p].empty()) { ll d = (calc(head,idx)+calc(head,E[p])-calc(E[p],idx))/2; int v = E[p]; while(calc(head,p)<d) { p = ttis[p][dir[p][v]].second; } if (ttis[p].size()<=1) break; p = ttis[p][1-dir[p][v]].second; } add(p,idx,A,B,W); } }

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

citymapping.cpp: In function 'void add(int, int, int*, int*, int*)':
citymapping.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<ttis[pp].size();i++) if (ttis[pp][i].second==p) {
                      ~^~~~~~~~~~~~~~~~
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:69:16: error: 'n' was not declared in this scope
     for (i=1;i<n;i++) {
                ^
citymapping.cpp:77:16: error: 'n' was not declared in this scope
     for (i=0;i<n;i++) {
                ^
citymapping.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j=2;j<lis.size();j++) {
              ~^~~~~~~~~~~
citymapping.cpp:93:12: warning: unused variable 'mini' [-Wunused-variable]
         ll mini = LINF;
            ^~~~