oj.uz

Submission #313003

# Submission time Handle Problem Language Result Execution time Memory
313003 2020-10-14T22:55:30 Z DanerZein Stations (IOI20_stations) C++14
10 / 100
 933 ms 900 KB 
#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
vector<int> labels;
vector<vi>G;
int vis[1010];
// task 3
/*void dfs(int u,int ns,int d){ 
  vis[u]=1;
  labels[u]=(1000*d+ns);
  for(auto &v:G[u]){
    if(!vis[v]){
      dfs(v,ns,d+1);
    }
  }
}
void asignar(int u){
  int ns=1;
  labels[u]=0;
  memset(vis,0,sizeof vis);
  vis[u]=1;
  for(auto &v:G[u]){
    dfs(v,ns,0);
    ns++;
  }
}*/
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  labels.assign(n,-1);
  G.clear();
  G.resize(n+1);
  int t=u.size();
  for(int i=0;i<t;i++){
    int x=u[i],y=v[i];
    G[x].push_back(y);
    G[y].push_back(x);
  }
  // 10 points - task 4
  labels[0]=1;
  memset(vis,0,sizeof vis);
  queue<ii> q;
  q.push(ii(0,1));
  while(!q.empty()){
    int id=q.front().first;
    int nl=q.front().second;
    q.pop();
    labels[id]=nl;
    int lr=nl*8;
    for(auto &v:G[id]){
      if(labels[v]==-1){
	q.push(ii(v,lr));
	lr++;
      }
    }
  }
  // 13 points - task 3
  /*int id=0;
  for(int i=0;i<n;i++){
    if(G[i].size()>2){
      id=i;
       break;
    }
  }
  asignar(id);*/
  // 8 points - taks 2
  /*for(int i=0;i<n;i++) labels[i]=i;*/
  // 5 points - task 1
  /*int no=0,id=-1;
  for(int i=0;i<n;i++){
    if(G[i].size()==1){
      id=i;
      break;
    }
  }
  queue<int> q;
  q.push(id);
  while(!q.empty()){
    int x=q.front();
    q.pop();
    labels[x]=no;
    no++;
    for(auto &v:G[x]){
      if(labels[v]==-1){
	q.push(v);
      }
    }
  }*/
  return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
  // 5 points - task 1
  /*  if(s>t)
    return s-1;
  return s+1;*/
  // 8 points - task 2
  /*queue<ii> q;
  q.push(ii(s*2+1,0));
  q.push(ii(s*2+2,1));
  int res=-1;
  while(!q.empty()){
    int x=q.front().first;
    int sw=q.front().second;
    if(x==t){
      res=sw;
      break;
    }
    q.pop();
    if(x*2+1<=t) q.push(ii(x*2+1,sw));
    if(x*2+2<=t) q.push(ii(x*2+2,sw));
  }
  if(res==-1){
    return c[0];
  }
  else{
    if(s==0){
      if(res==0) return c[0];
      return c[1];
    }
    if(res==0) return c[1];
    else return c[2];
  }*/
  // 16 points - task 3
  /*if(s==0){
    for(int i=0;i<c.size();i++){
      if(c[i]%1000==t%1000){
	return c[i];
      }
    }
  }
  else{
    if(s%1000==t%1000){
      if(s<t)
	return s+1000;
      return max(0,s-1000);
    }
    else{
      return max(0,s-1000);
    }
    }*/
  // 10 points - task 4
  //cout<<s<<" "<<t<<endl;
  int ls;
  while(t!=0){
    ls=t;
    t/=8;
    // cout<<t<<endl;
    if(t<=s) break; 
  }
  if(t==s) return ls;
  else return s/8;
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:153:19: warning: 'ls' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |   if(t==s) return ls;
      |                   ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=36864
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 468 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=15, label=4096
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Invalid labels (duplicates values). scenario=1, label=0
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 640 KB Output is correct
2 Correct 633 ms 640 KB Output is correct
3 Correct 596 ms 644 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 601 ms 640 KB Output is correct
8 Correct 933 ms 760 KB Output is correct
9 Correct 663 ms 640 KB Output is correct
10 Correct 600 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 900 KB Output is correct
14 Correct 3 ms 776 KB Output is correct
15 Correct 2 ms 648 KB Output is correct
16 Correct 544 ms 640 KB Output is correct
17 Correct 493 ms 652 KB Output is correct
18 Correct 499 ms 832 KB Output is correct
19 Correct 520 ms 644 KB Output is correct
20 Correct 602 ms 644 KB Output is correct

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Invalid labels (duplicates values). scenario=1, label=0
2 Halted 0 ms 0 KB -