oj.uz

Submission #313223

# Submission time Handle Problem Language Result Execution time Memory
313223 2020-10-15T14:24:24 Z NhatMinh0208 Stations (IOI20_stations) C++14
100 / 100
 1131 ms 5980 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; gt[i].clear();}
  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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 5736 KB Output is correct
2 Correct 468 ms 5760 KB Output is correct
3 Correct 921 ms 5376 KB Output is correct
4 Correct 657 ms 5632 KB Output is correct
5 Correct 599 ms 5584 KB Output is correct
6 Correct 450 ms 5732 KB Output is correct
7 Correct 461 ms 5632 KB Output is correct
8 Correct 5 ms 5588 KB Output is correct
9 Correct 7 ms 5588 KB Output is correct
10 Correct 4 ms 5376 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 5520 KB Output is correct
2 Correct 570 ms 5656 KB Output is correct
3 Correct 1012 ms 5588 KB Output is correct
4 Correct 657 ms 5588 KB Output is correct
5 Correct 628 ms 5580 KB Output is correct
6 Correct 481 ms 5528 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 5632 KB Output is correct
2 Correct 462 ms 5724 KB Output is correct
3 Correct 892 ms 5424 KB Output is correct
4 Correct 675 ms 5588 KB Output is correct
5 Correct 721 ms 5736 KB Output is correct
6 Correct 547 ms 5616 KB Output is correct
7 Correct 577 ms 5744 KB Output is correct
8 Correct 5 ms 5588 KB Output is correct
9 Correct 9 ms 5704 KB Output is correct
10 Correct 4 ms 5584 KB Output is correct
11 Correct 663 ms 5376 KB Output is correct
12 Correct 484 ms 5632 KB Output is correct
13 Correct 571 ms 5724 KB Output is correct
14 Correct 536 ms 5524 KB Output is correct
15 Correct 73 ms 5576 KB Output is correct
16 Correct 87 ms 5504 KB Output is correct
17 Correct 129 ms 5376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 5732 KB Output is correct
2 Correct 741 ms 5588 KB Output is correct
3 Correct 769 ms 5584 KB Output is correct
4 Correct 5 ms 5592 KB Output is correct
5 Correct 7 ms 5440 KB Output is correct
6 Correct 4 ms 5504 KB Output is correct
7 Correct 655 ms 5724 KB Output is correct
8 Correct 963 ms 5376 KB Output is correct
9 Correct 711 ms 5760 KB Output is correct
10 Correct 658 ms 5588 KB Output is correct
11 Correct 9 ms 5588 KB Output is correct
12 Correct 9 ms 5504 KB Output is correct
13 Correct 8 ms 5504 KB Output is correct
14 Correct 7 ms 5716 KB Output is correct
15 Correct 5 ms 5584 KB Output is correct
16 Correct 490 ms 5584 KB Output is correct
17 Correct 621 ms 5592 KB Output is correct
18 Correct 615 ms 5588 KB Output is correct
19 Correct 509 ms 5584 KB Output is correct
20 Correct 624 ms 5592 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 5632 KB Output is correct
2 Correct 543 ms 5736 KB Output is correct
3 Correct 1131 ms 5584 KB Output is correct
4 Correct 872 ms 5588 KB Output is correct
5 Correct 658 ms 5504 KB Output is correct
6 Correct 482 ms 5728 KB Output is correct
7 Correct 554 ms 5512 KB Output is correct
8 Correct 5 ms 5584 KB Output is correct
9 Correct 7 ms 5724 KB Output is correct
10 Correct 4 ms 5584 KB Output is correct
11 Correct 469 ms 5376 KB Output is correct
12 Correct 551 ms 5720 KB Output is correct
13 Correct 1062 ms 5588 KB Output is correct
14 Correct 723 ms 5584 KB Output is correct
15 Correct 611 ms 5588 KB Output is correct
16 Correct 493 ms 5504 KB Output is correct
17 Correct 628 ms 5388 KB Output is correct
18 Correct 521 ms 5864 KB Output is correct
19 Correct 447 ms 5628 KB Output is correct
20 Correct 514 ms 5584 KB Output is correct
21 Correct 65 ms 5580 KB Output is correct
22 Correct 76 ms 5536 KB Output is correct
23 Correct 114 ms 5536 KB Output is correct
24 Correct 11 ms 5504 KB Output is correct
25 Correct 8 ms 5588 KB Output is correct
26 Correct 7 ms 5376 KB Output is correct
27 Correct 6 ms 5376 KB Output is correct
28 Correct 4 ms 5592 KB Output is correct
29 Correct 524 ms 5616 KB Output is correct
30 Correct 517 ms 5376 KB Output is correct
31 Correct 583 ms 5376 KB Output is correct
32 Correct 699 ms 5596 KB Output is correct
33 Correct 571 ms 5504 KB Output is correct
34 Correct 332 ms 5632 KB Output is correct
35 Correct 447 ms 5632 KB Output is correct
36 Correct 483 ms 5980 KB Output is correct
37 Correct 452 ms 5616 KB Output is correct
38 Correct 481 ms 5856 KB Output is correct
39 Correct 599 ms 5632 KB Output is correct
40 Correct 599 ms 5860 KB Output is correct
41 Correct 471 ms 5748 KB Output is correct
42 Correct 85 ms 5528 KB Output is correct
43 Correct 130 ms 5504 KB Output is correct
44 Correct 147 ms 5632 KB Output is correct
45 Correct 182 ms 5632 KB Output is correct
46 Correct 375 ms 5528 KB Output is correct
47 Correct 320 ms 5636 KB Output is correct
48 Correct 83 ms 5632 KB Output is correct
49 Correct 67 ms 5632 KB Output is correct