oj.uz

Submission #313219

# Submission time Handle Problem Language Result Execution time Memory
313219 2020-10-15T14:20:01 Z NhatMinh0208 Stations (IOI20_stations) C++14
8 / 100
 994 ms 5712 KB 
/*
khoi orz, go check out his algo
-normie-
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define FILE_IN "ninja.inp"
#define FILE_OUT "ninja.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define nfio cin.tie(0);cout.tie(0)
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define ord(a,b,c) ((a>=b)and(b>=c))
#define MOD (ll(1000000007))
#define MAX 300001
#define mag 1048576
#define fi first
#define se second
#define pow2(x) (ll(1)<<x)
#define pii pair<int,int>
#define piii pair<int,pii>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define For(i,__,___) for(int i=__;i<=___;i++)
#define Rep(i,__,___) for(int i=__;i>=___;i--)
#define ordered_set tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update>
#define endl "\n"
#define bi BigInt
#define ll long long
#define pi 3.1415926535897
//------START-----------//
vector<int> gt[100001];
int used[100001],label_result[100001],t;
//------END-----------//
void dfs1(int x, int parity)
{
  used[x]=1;
  if (parity==0)
  {
    label_result[x]=t;
    t++;
  }
  for (int g : gt[x]) if (!used[g])
  {
    dfs1(g,1-parity);
  }
  if (parity==1)
  {
    label_result[x]=t;
    t++;
  }
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
  t=0;
  for (int i=0;i<n;i++) used[i]=0;
  for (int i=0;i<n-1;i++)
  {
    gt[u[i]].push_back(v[i]);
    gt[v[i]].push_back(u[i]);
  }
  dfs1(0,0);
  vector<int> res;
  for (int i=0;i<n;i++)
  {
    res.push_back(label_result[i]);
  }
  return res;
}
int find_next_station(int s, int t, vector<int> c)
{
  sort(c.begin(),c.end());
  if (c.size()==1) return c[0];
  else if (s==0)
  {
    for (int i=0;i<c.size();i++) if (t<=c[i]) return c[i];
  }
  else if (s<c[0])
  {
    if ((t<s)or(t>c[c.size()-2])) return c[c.size()-1];
    else for (int i =0;i<=c.size()-2;i++) if (t<=c[i]) return c[i];
  }
  else
  {
    if ((t>s)or(t<c[1])) return c[0];
    else for (int i =c.size()-1;i>=1;i--) if (t>=c[i]) return c[i];
  }
}

Compilation message

stations.cpp:8: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    8 | #pragma comment(linker, "/stack:200000000")
      | 
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i=0;i<c.size();i++) if (t<=c[i]) return c[i];
      |                  ~^~~~~~~~~
stations.cpp:86:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     else for (int i =0;i<=c.size()-2;i++) if (t<=c[i]) return c[i];
      |                        ~^~~~~~~~~~~~
stations.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
   93 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 571 ms 5616 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 5616 KB Output is correct
2 Correct 564 ms 5504 KB Output is correct
3 Correct 994 ms 5584 KB Output is correct
4 Correct 741 ms 5588 KB Output is correct
5 Correct 607 ms 5624 KB Output is correct
6 Correct 504 ms 5528 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 560 ms 5648 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 5712 KB Output is correct
2 Incorrect 691 ms 5376 KB Wrong query response.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 539 ms 5656 KB Wrong query response.
2 Halted 0 ms 0 KB -