oj.uz

Submission #312986

# Submission time Handle Problem Language Result Execution time Memory
312986 2020-10-14T22:12:18 Z DanerZein Stations (IOI20_stations) C++14
16 / 100
 1126 ms 1024 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];
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;
  //cout<<u<<endl;
  for(auto &v:G[u]){
    // cout<<v<<" ";
    dfs(v,ns,0);
    ns++;
  }
  //cout<<endl;
  //cout<<ns<<endl;
}
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);
  }
  // 13 points - task 3
  int id=0;
  for(int i=0;i<n;i++){
    if(G[i].size()>2){
      id=i;
       break;
    }
  }
  //cout<<endl;
  asignar(id);
  /*for(int i=0;i<n;i++) cout<<labels[i]<<" ";
  cout<<endl;*/
  // 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);
    }
  }
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(int i=0;i<c.size();i++){
      |                 ~^~~~~~~~~
stations.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
  132 | }
      | ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 1024 KB Output is correct
2 Correct 534 ms 776 KB Output is correct
3 Correct 922 ms 644 KB Output is correct
4 Correct 729 ms 1020 KB Output is correct
5 Correct 652 ms 640 KB Output is correct
6 Correct 496 ms 768 KB Output is correct
7 Correct 459 ms 788 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 652 ms 640 KB Output is correct
12 Correct 530 ms 768 KB Output is correct
13 Correct 472 ms 996 KB Output is correct
14 Correct 455 ms 820 KB Output is correct
15 Correct 69 ms 896 KB Output is correct
16 Correct 85 ms 768 KB Output is correct
17 Correct 108 ms 812 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 768 KB Output is correct
2 Correct 673 ms 892 KB Output is correct
3 Correct 569 ms 640 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 619 ms 652 KB Output is correct
8 Correct 934 ms 640 KB Output is correct
9 Correct 698 ms 640 KB Output is correct
10 Correct 612 ms 640 KB Output is correct
11 Incorrect 1 ms 256 KB Invalid labels (duplicates values). scenario=5, label=1001
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 567 ms 768 KB Partially correct
2 Partially correct 470 ms 1008 KB Partially correct
3 Correct 993 ms 640 KB Output is correct
4 Partially correct 824 ms 672 KB Partially correct
5 Partially correct 577 ms 640 KB Partially correct
6 Partially correct 472 ms 772 KB Partially correct
7 Partially correct 453 ms 800 KB Partially correct
8 Partially correct 3 ms 648 KB Partially correct
9 Partially correct 4 ms 640 KB Partially correct
10 Partially correct 1 ms 652 KB Partially correct
11 Incorrect 5 ms 384 KB Invalid labels (duplicates values). scenario=0, label=2001
12 Halted 0 ms 0 KB -