Submission #564817

#TimeUsernameProblemLanguageResultExecution timeMemory
564817hoanghq2004Rail (IOI14_rail)C++14
56 / 100
983 ms98892 KiB
/* 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]; 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]; }; location[0] = first; stype[0] = 1; for (int i = 0; i < n; ++i) mind[i] = 1e9; auto add = [&](int u) { for (int v = 0; v < n; ++v) mind[v] = min(mind[v], get(u, v)); vis[u] = 1; }; add(0); for (int T = 1; T < n; ++T) { int u = -1; for (int v = 0; v < n; ++v) if (vis[v] == 0 && (u == -1 || mind[u] > mind[v])) u = v; int v = -1; for (int w = 0; w < n; ++w) if (vis[w] && get(u, w) == mind[u]) v = w; stype[u] = 3 - stype[v]; if (stype[u] == 2) location[u] = location[v] + get(u, v); else location[u] = location[v] - get(u, v); add(u); } // for (int u = 0; u < n; ++u) cout << location[u] << ' '; } #ifdef LOCAL void getInput() { 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 (i = 0; i < S; i++) if(type[i]!=stations[i].type || location[i]!=stations[i].location) ok = 0; if(ok==0) printf("Incorrect"); else printf("Correct"); return 0; } #endif // LOCAL
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...