Submission #672631

#	Time	Username	Problem	Language	Result	Execution time	Memory
672631		tbzard	Stations (IOI20_stations)	C++14	0 / 100	131 ms	40176 KiB

stations

#include <bits/stdc++.h>
using namespace std;

vector<int> g[1002];
int best[12][1002][1002];
int comp[10002];
int node[10002];
int color[12][1002];
int b = 0, idx = 0;
vector<int> label(int n, int k, vector<int> u, vector<int> v){
    memset(best[idx], -1, sizeof(best[idx]));
    vector<int> ans(n);
    for(int i=0;i<n;i++){
        ans[i] = b;
        comp[b] = idx;
        node[b] = i;
        color[idx][i] = b;
        b++;
    }
    for(int i=0;i<n;i++){
        g[i].clear();
    }
    for(int i=0;i<u.size();i++){
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    for(int i=0;i<n;i++){
        queue<int> q;
        q.push(i);
        best[idx][i][i] = 0;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int j=0;j<g[u].size();j++){
                int v = g[u][j];
                if(best[idx][i][v] == -1){
                    best[idx][i][v] = best[idx][i][u] + 1;
                    q.push(v);
                }
            }
        }
    }
    idx++;
    return ans;
}
int find_next_station(int s, int t, vector<int> c){
    int idx = comp[s];
    s = node[s], t = node[t];
    for(int i=0;i<c.size();i++){
        int v = node[c[i]];
        if(best[idx][s][t]-1 == best[idx][s][v]) return c[i];
    }
}

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<u.size();i++){
      |                 ~^~~~~~~~~
stations.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             for(int j=0;j<g[u].size();j++){
      |                         ~^~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<c.size();i++){
      |                 ~^~~~~~~~~
stations.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61