제출 #93561

#제출 시각아이디문제언어결과실행 시간메모리
93561muradeynEvacuation plan (IZhO18_plan)C++14
0 / 100
311 ms49728 KiB
/* Murad Eynizade */ #include <bits/stdc++.h> #define int long long #define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0); #define SIZE 100001 #define INF INT_MAX #define F first #define S second #define in(a) scanf("%d",&a); #define outn(a) printf("%d\n",&a); #define outs(a) printf("%d ",&a); #define LOG 18 using namespace std; int n , m , w , d[SIZE] , sze[SIZE] , par[SIZE] , lvl[SIZE] , p[SIZE][LOG] , q , ans , val[SIZE][LOG]; vector< pair<int,int> >v[SIZE]; vector< pair< int , pair<int,int> > >edges; priority_queue< pair<int,int> >pq; void init() { for (int i = 1;i<SIZE;i++) { d[i] = INF; sze[i] = 1; par[i] = i; } } void dijkstra() { while (!pq.empty()) { int u = pq.top().S, dd = pq.top().F; pq.pop(); if (dd != d[u]) continue; for (auto i : v[u]) { int to = i.first , we = i.second; if (d[to] > d[u] + we) { //cout<<to<<" "<<d[to]<<endl; //cout<<u<<" "<<d[u]<<endl; //cout<<we<<endl; //char aa; //cin>>aa; d[to] = d[u] + we; pq.push({-d[to] , to}); } } } } int find_root(int a) { if (a == par[a]) return a; return par[a] = find_root(par[a]); } void dfs(int s,int pa,int l) { lvl[s] = l; p[s][0] = pa; val[s][0] = d[s]; for (auto i : v[s]) { int to = i.F; if (to == pa)continue; dfs(to,s,l + 1); } } int lg(int x) { int ret = 0; while (x > 1) { ret++; x /= 2; } return ret; } int lca(int x,int y) { if (lvl[x] < lvl[y])swap(x,y); while (lvl[x] != lvl[y]) { int dist = lvl[x] - lvl[y]; int lg2 = lg(dist); ans = min(ans , val[x][lg2]); x = p[x][lg2]; ans = min(ans,d[x]); } if (x == y)return ans; for (int i = LOG - 1;i >= 0;i--) { if (p[x][i] != p[y][i]) { ans = min(ans , val[x][i]); x = p[x][i]; ans = min(ans,d[x]); ans = min(ans , val[y][i]); y = p[y][i]; ans = min(ans,d[y]); } } return min(ans,val[p[x][0]][0]); } int x,y; main() { FAST_READ; init(); cin>>n>>m; while (m--) { cin>>x>>y>>w; v[x].push_back({y,w}); v[y].push_back({x,w}); edges.push_back({-1,{x,y}}); } cin>>m; while (m--) { cin>>x; d[x] = 0; pq.push({0,x}); } dijkstra(); for (int i = 0;i<edges.size();i++) { edges[i].F = -min(d[edges[i].S.F] , d[edges[i].S.S]); } sort(edges.begin(),edges.end()); int co = 0; //for (int i = 1;i<=n;i++)cout<<i<<" "<<d[i]<<endl; for (int i = 1;i<=n;i++) v[i].clear(); for (auto i : edges) { int roota = find_root(i.S.F); int rootb = find_root(i.S.S); if (roota == rootb) continue; //cout<<i.S.F<<" "<<i.S.S<<endl; v[i.S.F].push_back({i.S.S,-1}); v[i.S.S].push_back({i.S.F,-1}); if (sze[i.S.F] < sze[i.S.S]) { sze[i.S.S] += sze[i.S.F]; par[roota] = rootb; } else { sze[i.S.F] += sze[i.S.S]; par[rootb] = roota; } co++; if (co == n - 1)break; } memset(p,-1,sizeof(p)); dfs(1,-1,1); for (int j = 1;j < LOG;j++) { for (int i = 1;i<=n;i++) { if (p[i][j - 1] == -1)p[i][j] = -1; else p[i][j] = p[p[i][j - 1]][j - 1]; } } for (int j = 1;j < LOG;j++) { for (int i = 1;i<=n;i++) { if (p[i][j - 1] == -1)val[i][j] = val[i][j - 1]; else val[i][j] = min(val[i][j - 1],val[p[i][j - 1]][j - 1]); } } cin>>q; while (q--) { cin>>x>>y; ans = min(d[x],d[y]); cout<<lca(x,y)<<endl; } return 0; }

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

plan.cpp:102:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0;i<edges.size();i++) {
                    ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...