oj.uz

Submission #565138

# Submission time Handle Problem Language Result Execution time Memory
565138 2022-05-20T10:44:22 Z hoanghq2004 Rail (IOI14_rail) C++14
100 / 100
 193 ms 99148 KB 
/* This is sample grader for the contestant */
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#ifndef LOCAL
#include "rail.h"

#endif // LOCAL
#ifdef LOCAL

typedef struct Station {
  int index;
  int type;
  int location;
  int L,R;
}STATION;
long long cnt;
static int S,SUBTASK;
static STATION stations[10004];

int cmp_fun_1(const void *a,const void *b)
{
	STATION c,d;
	c = *(STATION*)(a);
	d = *(STATION*)(b);
  	return c.location < d.location ? -1 : 1;
}

int cmp_fun_2(const void *a,const void *b)
{
	STATION c,d;
	c = *(STATION*)(a);
	d = *(STATION*)(b);
  	return c.index < d.index ? -1 : 1;
}

void now_I_want_to_getLR(){
  int now = stations[S-1].index,i;
  for(i=S-2;i>=0;i--){
    stations[i].R = now;
    if(stations[i].type==2)	now = stations[i].index;
  }
  now = stations[0].index;
  for(i=1;i<S;i++){
    stations[i].L = now;
    if(stations[i].type==1)	now = stations[i].index;
  }
}

int getDistance(int x,int y)
{
  cnt++;
  if(x==y)	return 0;
  if(x<0 || x>=S || y<0 || y>=S)    return -1;
  if(stations[x].location > stations[y].location){
  	int tmp = x;
	x = y;
	y = tmp;
  }
  int ret = 0;
  if(stations[x].type==1 && stations[y].type==1){
    ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
  }else if(stations[x].type==1 && stations[y].type==2){
    ret = stations[y].location-stations[x].location;
  }else if(stations[x].type==2 && stations[y].type==2){
    ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
  }else if(stations[x].type==2 && stations[y].type==1){
    ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
      -stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
  }
  return ret;
}
#endif

const int N = 5010;
int d[N][N];

int par[N];

int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}

int Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return 0;
    par[v] = u;
    return 1;
}

int vis[N], mind[N];
int lft[N];

void findLocation(int n, int first, int location[], int stype[]) {
    memset(d, -1, sizeof(d));
    auto get = [&](int u, int v) {
        if (u == v) return 0;
        if (u > v) swap(u, v);
        if (d[u][v] == -1) d[u][v] = getDistance(u, v);
        return d[u][v];
    };
    int x = 0, y = 0;
    for (int z = 1; z < n; ++z)
        if (y == 0 || get(x, y) > get(x, z)) y = z;
    location[x] = first, location[y] = location[x] + get(x, y);
    stype[x] = 1, stype[y] = 2;
    vector <pair <int, int>> work;
    for (int z = 0; z < n; ++z) {
        if (z == x || z == y) continue;
        if (get(x, y) > get(z, y) && get(x, z) == get(y, z) + get(x, y)) {
            location[z] = location[y] - get(y, z);
            stype[z] = 1;
        } else work.push_back({get(x, z), z});
    }
    set <pair <int, int>> C, D;
    int rm = x;
    for (int i = 0; i < n; ++i) {
        if (stype[i] == 1) {
            C.insert({location[i], i});
            if (location[i] > location[rm]) rm = i;
        } else if (stype[i] == 2) D.insert({location[i], i});
    }
//    for (int i = 0; i < n; ++i) cout << location[i] << ' ';
//    cout << '\n';
//    cout << location[x] << ' ' << location[y] << '\n';
    sort(work.begin(), work.end());
    for (auto [_, z]: work) {
        if (get(x, z) >= get(x, y) + get(y, z)) { // left
            lft[z] = 1;
            if (C.empty() || C.begin() -> first >= location[x]) {
                stype[z] = 1;
                location[z] = location[y] - get(y, z);
            } else {
                int t = C.begin() -> second;
                for (int s = 0; s < n; ++s) {
                    if (stype[s] != 1) continue;
                    if (get(y, z) + 2 * location[s] == location[y] + location[t] + get(t, z)) {
                        stype[z] = 2;
                        location[z] = get(t, z) + location[t];
                        break;
                    }
                }
                if (stype[z] == 0) {
                    stype[z] = 1;
                    location[z] = location[y] - get(y, z);
                }
            }
        } else { // right
            if (D.empty() || (--D.end()) -> first <= location[y]) {
                stype[z] = 2;
                location[z] = location[x] + get(x, z);
            } else {
                int t = (--D.end()) -> second;
                for (int s = 0; s < n; ++s) {
                    if (stype[s] != 2) continue;
                    if (get(x, z) - 2 * location[s] == - location[x] - location[t] + get(t, z)) {
                        stype[z] = 1;
                        location[z] = location[t] - get(t, z);
                        break;
                    }
                }
                if (stype[z] == 0) {
                    stype[z] = 2;
                    location[z] = location[x] + get(x, z);
                }
            }
        }
        if (stype[z] == 1) C.insert({location[z], z});
        else D.insert({location[z], z});
    }
//    for (int i = 0; i < n; ++i) cout << location[i] << ' ';
//    cout << '\n';
//    cout << x << ' ' << y << '\n';
}
#ifdef LOCAL


void getInput()
{
    freopen("IOI14_rail.inp", "r", stdin);
  int g;
  g = scanf("%d",&SUBTASK);
  g = scanf("%d",&S);
  int s;
  for (s = 0; s < S; s++) {
    int type, location;
    g = scanf(" %d %d",&type,&location);
    stations[s].index = s;
    stations[s].location = location;
    stations[s].type = type;
    stations[s].L = -1;
    stations[s].R = -1;
  }
  qsort(stations, S, sizeof(STATION), cmp_fun_1);
  now_I_want_to_getLR();
  qsort(stations, S, sizeof(STATION), cmp_fun_2);
}

int serverGetStationNumber()
{
  return S;
}

int serverGetSubtaskNumber()
{
  return SUBTASK;
}

int serverGetFirstStationLocation()
{
  return stations[0].location;
}

int main()
{
  int i;
  getInput();
  cnt = 0;

  int location[10005];
  int type[10005];
  int ok = 1;
  findLocation(S, serverGetFirstStationLocation(),location, type);
  if(SUBTASK==3 && cnt>S*(S-1))	ok = 0;
  if(SUBTASK==4 && cnt>3*(S-1))	ok = 0;
//    for (int i = 0; i < S; ++i) {
//        if (stations[0].location <= stations[i].location && stations[i].location <= stations[2339].location) {
////        assert(type[i] == stations[i].type);
////        assert(location[i] == stations[i].location);
////            continue;
//        }
////        if (stations[0].location > stations[i].location) {
////            assert(lft[i] == 1 && stations[i].type == type[i]);
////        }
////        \else assert(lft[i] == 0);
////        if (stations[0])
////        assert(type[i] == stations[i].type);
//    }
  for (i = 0; i < S; i++)
    if(type[i]!=stations[i].type || location[i]!=stations[i].location) {
//        cout << i << '\n';
      ok = 0;
    }
//    assert(ok);
  if(ok==0)	printf("Incorrect");
  else	printf("Correct");
  return 0;
}
#endif // LOCAL

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:126:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |     for (auto [_, z]: work) {
      |               ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98508 KB Output is correct
2 Correct 38 ms 98508 KB Output is correct
3 Correct 39 ms 98584 KB Output is correct
4 Correct 38 ms 98608 KB Output is correct
5 Correct 50 ms 98512 KB Output is correct
6 Correct 39 ms 98508 KB Output is correct
7 Correct 46 ms 98560 KB Output is correct
8 Correct 40 ms 98636 KB Output is correct
9 Correct 39 ms 98516 KB Output is correct
10 Correct 39 ms 98512 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98540 KB Output is correct
2 Correct 38 ms 98588 KB Output is correct
3 Correct 48 ms 98596 KB Output is correct
4 Correct 52 ms 98524 KB Output is correct
5 Correct 39 ms 98508 KB Output is correct
6 Correct 39 ms 98512 KB Output is correct
7 Correct 40 ms 98516 KB Output is correct
8 Correct 39 ms 98588 KB Output is correct
9 Correct 38 ms 98680 KB Output is correct
10 Correct 42 ms 98600 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 98936 KB Output is correct
2 Correct 148 ms 98936 KB Output is correct
3 Correct 149 ms 99056 KB Output is correct
4 Correct 161 ms 99048 KB Output is correct
5 Correct 153 ms 98992 KB Output is correct
6 Correct 151 ms 98976 KB Output is correct
7 Correct 172 ms 98940 KB Output is correct
8 Correct 169 ms 99020 KB Output is correct
9 Correct 153 ms 99004 KB Output is correct
10 Correct 146 ms 98952 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 99028 KB Output is correct
2 Correct 159 ms 98944 KB Output is correct
3 Correct 151 ms 98952 KB Output is correct
4 Correct 174 ms 99000 KB Output is correct
5 Correct 162 ms 99148 KB Output is correct
6 Correct 149 ms 99016 KB Output is correct
7 Correct 156 ms 98932 KB Output is correct
8 Correct 172 ms 99048 KB Output is correct
9 Correct 173 ms 98936 KB Output is correct
10 Correct 151 ms 99024 KB Output is correct
11 Correct 149 ms 98944 KB Output is correct
12 Correct 163 ms 98956 KB Output is correct
13 Correct 148 ms 98952 KB Output is correct
14 Correct 144 ms 99072 KB Output is correct
15 Correct 156 ms 99008 KB Output is correct
16 Correct 193 ms 98944 KB Output is correct
17 Correct 144 ms 98940 KB Output is correct
18 Correct 150 ms 99072 KB Output is correct
19 Correct 169 ms 98928 KB Output is correct
20 Correct 150 ms 98944 KB Output is correct