oj.uz

Submission #745641

# Submission time Handle Problem Language Result Execution time Memory
745641 2023-05-20T17:24:27 Z Username4132 Rail (IOI14_rail) C++14
30 / 100
 299 ms 98848 KB 
#include "rail.h"
#include<iostream>
#include<vector>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN=5010, INF=1000000010;
int *rel, *res;
int n, dis[MAXN][MAXN];
bool vis[MAXN];
vector<pii> g[MAXN];

void dfs(int v){
    vis[v]=true;
    for(pii to:g[v]) if(!vis[to.F]){
        if(res[v]==1) rel[to.F]=rel[v]+to.S;
        else rel[to.F]=rel[v]-to.S;
        res[to.F] = res[v]==1? 2 : 1;
        dfs(to.F);
    }
}

void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    forn(i, n) forsn(j, i, n) dis[i][j]=dis[j][i]=getDistance(i, j);
    forn(i, n){
        int mn=INF, ind=-1;
        forn(j, n) if(j!=i && mn>dis[i][j]) mn=dis[i][j], ind=j;
        g[i].PB({ind, mn}), g[ind].PB({i, mn});
    }
    rel=location, res=stype;
    rel[0]=first, res[0]=1;
    dfs(0);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 884 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 884 KB Output is correct
10 Correct 1 ms 880 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 ms 98796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 299 ms 98848 KB Output isn't correct
2 Halted 0 ms 0 KB -