Submission #1344590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344590		SmuggingSpun	Currents (EGOI25_currents)	C++20	100 / 100	125 ms	36292 KiB

Main

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
template<class T>bool minimize(T& a, T b){
  if(a > b){
    a = b;
    return true;
  }
  return false;
}
const int lim = 2e5 + 5;
const int INF = 1e9;
int n, m;
vector<int>g[2][lim];
namespace sub1{
  void solve(){
    if(n == 2){
      return void(cout << 1);
    }
    for(int i = n - 1; i > 0; i--){
      cout << i + n - 3 << " ";
    }
  }
}
namespace sub2{
  bool check_subtask(){
    return g[1][n - 1].size() == n - 1;
  }
  void solve(){
    vector<int>f(n, -1);
    queue<int>q;
    q.push(f[0] = 0);
    while(!q.empty()){
      int u = q.front();
      q.pop();
      for(int& v : g[0][u]){
        if(f[v] == -1){
          f[v] = f[u] + 1;
          q.push(v);
        }
      }
    }
    cout << "1 ";
    for(int i = 1; i < n - 1; i++){
      cout << f[i] << " ";
    }
  }
}
namespace sub345{
  vector<int>event[lim << 1];
  void solve(){
    vector<int>f(n, -1);
    queue<int>q;
    q.push(f[0] = 0);
    while(!q.empty()){
      int u = q.front();
      q.pop();
      for(int& v : g[0][u]){
        if(f[v] == -1){
          f[v] = f[u] + 1;
          q.push(v);
        }
      }
    }
    vector<int>nf(n, INF);
    event[nf[n - 1] = 0].push_back(n - 1);
    for(int d = 0; d < (lim << 1); d++){
      for(int& u : event[d]){
        if(d == nf[u]){
          for(int& v : g[1][u]){
            if(minimize(nf[v], max(d + 1, f[v]))){
              event[nf[v]].push_back(v);
            }
          }
        }
      }
    }
    for(int i = 0; i < n - 1; i++){
      cout << max(1, nf[i]) << " ";
    }
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  cin >> n >> m;
  bool is_sub1 = true;
  for(int i = 0; i < m; i++){
    int a, b;
    cin >> a >> b;
    g[0][a].push_back(b);
    g[1][b].push_back(a);
    if(a != i || b != i + 1){
      is_sub1 = false;
    }
  }
  if(is_sub1){
    sub1::solve();
  }
  else if(sub2::check_subtask()){
    sub2::solve();
  }
  else{
    sub345::solve();
  }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:86:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 29 / 29
• Subtask 6: 24 / 24