Submission #657839

#TimeUsernameProblemLanguageResultExecution timeMemory
657839activedeltorreSwapping Cities (APIO20_swap)C++14
7 / 100
1241 ms524288 KiB
#include "swap.h" #include <fstream> #include <vector> #include <algorithm> using namespace std; //ifstream cin("a.in"); //ofstream cout("a.out"); vector<pair<int,pair<int,int> > >edges; bool cmp(pair<int,pair<int,int> >a,pair<int,pair<int,int> >b) { return a.first<b.first; } vector<pair<int,long long> >adj[200005]; vector<long long>vec; long long rasp[200005]; long long jos[200005]; long long sus[200005]; long long lvl[200005]; long long inf=1e14; void dfs(int curr,int parent) { int i,k; lvl[curr]=lvl[parent]+1; vec.clear(); if(adj[curr].size()>=3) { for(i=0; i<adj[curr].size(); i++) { vec.push_back(adj[curr][i].second); } sort(vec.begin(),vec.end()); jos[curr]=vec[2]; } else { jos[curr]=inf; } for(i=0; i<adj[curr].size(); i++) { k=adj[curr][i].first; if(k!=parent) { dfs(k,curr); } jos[curr]=min(jos[curr],max(jos[curr],adj[curr][i].second)); } } void dfs2(int curr,int par,long long val) { int i,k; sus[curr]=max(min(jos[par],sus[par]),val); rasp[curr]=min(sus[curr],jos[curr]); for(i=0; i<adj[curr].size(); i++) { k=adj[curr][i].first; if(k!=par) { dfs2(k,curr,adj[curr][i].second); } } } ///bl e parinte /// drum e cost de a merge la parinte /// ext e cost minim degreee 3 long long bl[33][200005]; long long ext[33][200005]; long long drum[33][200005]; void dfs3(int curr,int par,long long val) { int i,k; bl[0][curr]=par; ext[0][curr]=min(rasp[par],rasp[curr]); drum[0][curr]=val; for(i=1; i<=30; i++) { bl[i][curr]=bl[i-1][bl[i-1][curr]]; ext[i][curr]=min(ext[i-1][curr],ext[i-1][bl[i-1][curr]]); drum[i][curr]=max(drum[i-1][curr],drum[i-1][bl[i-1][curr]]); } for(i=0; i<adj[curr].size(); i++) { k=adj[curr][i].first; if(k!=par) { dfs3(k,curr,adj[curr][i].second); } } } int lca (int a,int b) { int i,curr; if(lvl[a]<lvl[b]) { swap(a,b); } for(i=30; i>=0; i--) { curr=bl[i][a]; if(lvl[curr]>=lvl[b]) { a=curr; } } if(a==b) { return a; } else { for(i=30; i>=0; i--) { if(bl[i][a]!=bl[i][b]) { a=bl[i][a]; b=bl[i][b]; } } return bl[0][a]; } } pair<long long,long long> calc (int a,int b) { long long curr,maxdrum=0,minrel=inf,i; for(i=30; i>=0; i--) { curr=bl[i][a]; if(lvl[curr]>=lvl[b]) { maxdrum=max(maxdrum,drum[i][a]); minrel=min(minrel,ext[i][a]); a=curr; } } return make_pair(maxdrum,minrel); } void init(int n, int m,vector<int> a, vector<int> b, vector<int> w) { int i; for(i=1; i<=m; i++) { a[i-1]++; b[i-1]++; adj[a[i-1]].push_back({b[i-1],w[i-1]}); adj[b[i-1]].push_back({a[i-1],w[i-1]}); // edges.push_back({w[i-1],{a[i-1],b[i-1]}}); } // sort(edges.begin(),edges.end(),cmp); sus[0]=inf; jos[0]=inf; dfs(1,0); dfs2(1,0,0); dfs3(1,0,0); } int getMinimumFuelCapacity(int x, int y) { int lc; x++; y++; pair<long long,long long>a; pair<long long,long long>b; lc=lca(x,y); a=calc(x,lc); b=calc(y,lc); a.first=max(a.first,b.first); a.second=min(a.second,b.second); a.first=max(a.first,b.second); if(a.first==inf) { return -1; } else { return a.first; } } /*int main() { int N, M; cin>>N>>M; vector<int> U(M), V(M), W(M); for (int i = 0; i < M; ++i) { cin>>U[i]>>V[i]>>W[i]; } int Q; cin>>Q; vector<int> X(Q), Y(Q); for (int i = 0; i < Q; ++i) { cin>>X[i]>>Y[i]; } init(N, M, U, V, W); vector<int> minimum_fuel_capacities(Q); for (int i = 0; i < Q; ++i) { minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]); } for (int i = 0; i < Q; ++i) { cout<<minimum_fuel_capacities[i]<<'\n'; } return 0; }*/

Compilation message (stderr)

swap.cpp: In function 'void dfs(int, int)':
swap.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(i=0; i<adj[curr].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
swap.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs2(int, int, long long int)':
swap.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs3(int, int, long long int)':
swap.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(i=0; i<adj[curr].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...
#Verdict Execution timeMemoryGrader output
Fetching results...