| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 68258 |
2018-08-16T10:22:32 Z |
KLPP |
Race (IOI11_race) |
C++14 |
|
4 ms |
724 KB |
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include "race.h"
using namespace std;
typedef long long int lld;
typedef pair<int,lld> pii;
int dist[300000];
lld dist2[300000];
int dist3[300000];
int k,n;
bool vale[300000];
int ans;
void decompor(vector<pii> nei[],int counter){
if(counter==0){
return;
}
for(int i=0;i<n;i++)dist[i]=-1;
for(int i=0;i<n;i++)dist2[i]=-1;
for(int i=0;i<n;i++)dist3[i]=-1;
for(int comeco=0;comeco<n;comeco++){
if(dist[comeco]==-1 && vale[comeco]){
int start=comeco;
dist[start]=-2;
queue<int>q;
q.push(start);
while(!q.empty()){
int node=q.front();q.pop();
start=node;
for(int i=0;i<nei[node].size();i++){
int u=nei[node][i].first;
if(dist[u]==-1 && vale[u]){
dist[u]=-2;
q.push(u);
}
}
}
dist[start]=0;
q.push(start);
while(!q.empty()){
int node=q.front();q.pop();
start=node;
for(int i=0;i<nei[node].size();i++){
int u=nei[node][i].first;
if(dist[u]==-2 && vale[u]){
dist[u]=dist[node]+1;
q.push(u);
}
}
}
int centroid=start;
for(int i=0;i<dist[start]/2;i++){
for(int j=0;j<nei[centroid].size();j++){
if(dist[nei[centroid][j].first]<dist[centroid] && vale[nei[centroid][j].first]){
centroid=nei[centroid][j].first;
j=1000000;
}
}
}
dist2[centroid]=0;
dist[centroid]=0;
int pointer=0;
map<lld,int> m;
vector<pair<lld,int > > V;vale[centroid]=false;
//for(int i=0;i<n;i++)cout<<vale[i]<<" ";
//cout<<endl;
for(int hh=nei[centroid].size()-1;hh>-1;hh--){
int v=nei[centroid][hh].first;
q.push(v);
dist3[v]=1;
dist2[v]=nei[centroid][hh].second;
while(!q.empty()){
int node=q.front();q.pop();
if(vale[node]){//cout<<node<<" ";
V.push_back(pair<lld,int>(dist2[node],dist3[node]));
if(dist2[node]==k && ans>=dist3[node] && vale[node]){
ans=min(ans,dist3[node]);
//cout<<centroid<<" P "<<node<<" "<<dist2[node]<<endl;
}
for(int i=0;i<nei[node].size();i++){
int u=nei[node][i].first;
if(dist2[u]==-1 && vale[u]){
dist3[u]=dist3[node]+1;
dist2[u]=dist2[node]+nei[node][i].second;
q.push(u);
}
}
}
}//cout<<endl;
for(int i=m.size();i<V.size();i++){
lld complemento=k-V[i].first;
std::map<lld,int>::iterator it=m.find(complemento);
if(it!=m.end()){//cout<<centroid<<" P "<<it->second<<" "<<V[i].second<<endl;
if(ans>it->second+V[i].second){
ans=min(ans,it->second+V[i].second);
//cout<<centroid<<" "<<it->second<<" "<<V[i].second<<endl;
}
}
}
for(int i=m.size();i<V.size();i++){
std::map<lld,int>::iterator it=m.find(V[i].first);
if(it==m.end()){
m[V[i].first]=V[i].second;
}else{
int h=it->second;
if(h>V[i].second)m[V[i].first]=V[i].second;
}
}
}
}
}//cout<<ans<<endl;
//for(int i=0;i<n;i++)cout<<vale[i]<<" ";
//cout<<endl;
counter--;//cout<<endl;
decompor(nei,counter);
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
vector<pii >nei[n];
for(int i=0;i<n-1;i++){
int x,y;
int z;
x=H[i][0];
y=H[i][1];
z=L[i];
nei[x].push_back(pair<int,lld>(y,z));
nei[y].push_back(pair<int,lld>(x,z));
}
vector<int>nodes;
for(int i=0;i<n;i++)vale[i]=true;
ans=10000000;
decompor(nei,30);
//cout<<ans<<endl;
if(ans<10000000)return ans;
else return -1;
}
/*int main(){
cin>>n>>k;
vector<pii >nei[n];
for(int i=0;i<n-1;i++){
int x,y;
int z;
cin>>x>>y>>z;
nei[x].push_back(pair<int,lld>(y,z));
nei[y].push_back(pair<int,lld>(x,z));
}
vector<int>nodes;
for(int i=0;i<n;i++)vale[i]=true;
ans=1000000;
decompor(nei,30);
if(ans<1000000)cout<<ans<<endl;
else cout<<-1<<endl;
return 0;
}*/
Compilation message
race.cpp: In function 'void decompor(std::vector<std::pair<int, long long int> >*, int)':
race.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<nei[node].size();i++){
~^~~~~~~~~~~~~~~~~
race.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<nei[node].size();i++){
~^~~~~~~~~~~~~~~~~
race.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<nei[centroid].size();j++){
~^~~~~~~~~~~~~~~~~~~~~
race.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<nei[node].size();i++){
~^~~~~~~~~~~~~~~~~
race.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=m.size();i<V.size();i++){
~^~~~~~~~~
race.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=m.size();i<V.size();i++){
~^~~~~~~~~
race.cpp:64:5: warning: unused variable 'pointer' [-Wunused-variable]
int pointer=0;
^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
520 KB |
Output is correct |
| 4 |
Correct |
2 ms |
520 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
3 ms |
600 KB |
Output is correct |
| 8 |
Correct |
3 ms |
600 KB |
Output is correct |
| 9 |
Correct |
2 ms |
600 KB |
Output is correct |
| 10 |
Correct |
2 ms |
648 KB |
Output is correct |
| 11 |
Correct |
3 ms |
648 KB |
Output is correct |
| 12 |
Correct |
2 ms |
648 KB |
Output is correct |
| 13 |
Correct |
2 ms |
724 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
520 KB |
Output is correct |
| 4 |
Correct |
2 ms |
520 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
3 ms |
600 KB |
Output is correct |
| 8 |
Correct |
3 ms |
600 KB |
Output is correct |
| 9 |
Correct |
2 ms |
600 KB |
Output is correct |
| 10 |
Correct |
2 ms |
648 KB |
Output is correct |
| 11 |
Correct |
3 ms |
648 KB |
Output is correct |
| 12 |
Correct |
2 ms |
648 KB |
Output is correct |
| 13 |
Correct |
2 ms |
724 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
520 KB |
Output is correct |
| 4 |
Correct |
2 ms |
520 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
3 ms |
600 KB |
Output is correct |
| 8 |
Correct |
3 ms |
600 KB |
Output is correct |
| 9 |
Correct |
2 ms |
600 KB |
Output is correct |
| 10 |
Correct |
2 ms |
648 KB |
Output is correct |
| 11 |
Correct |
3 ms |
648 KB |
Output is correct |
| 12 |
Correct |
2 ms |
648 KB |
Output is correct |
| 13 |
Correct |
2 ms |
724 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
4 ms |
520 KB |
Output is correct |
| 4 |
Correct |
2 ms |
520 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
600 KB |
Output is correct |
| 7 |
Correct |
3 ms |
600 KB |
Output is correct |
| 8 |
Correct |
3 ms |
600 KB |
Output is correct |
| 9 |
Correct |
2 ms |
600 KB |
Output is correct |
| 10 |
Correct |
2 ms |
648 KB |
Output is correct |
| 11 |
Correct |
3 ms |
648 KB |
Output is correct |
| 12 |
Correct |
2 ms |
648 KB |
Output is correct |
| 13 |
Correct |
2 ms |
724 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
724 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
