Submission #1339796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1339796		SmuggingSpun	Coin (NOI24_coin)	C++20	100 / 100	492 ms	34024 KiB

Main

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
template<class T>void maximize(T& a, T b){
  if(a < b){
    a = b;
  }
}
const int LIM = 8e5 + 5;
int n, m, x[LIM], y[LIM];
namespace sub123{
  const int lim = 1e3 + 5;
  vector<int>g[2][lim];
  bitset<lim>vis, d[2][lim];
  void dfs(const int id, int u){
    vis[u] = true;
    for(int& v : g[id][u]){
      if(!vis[v]){
        dfs(id, v);
      }
      d[id][u] |= d[id][v];
    }
  }
  void solve(){
    vector<int>ans(n + 1, -1);
    for(int i = 1; i <= m; i++){
      g[0][x[i]].push_back(y[i]);
      g[1][y[i]].push_back(x[i]);
      for(int j = 1; j <= n; j++){
        d[0][j].reset();
        d[1][j].reset();
        d[0][j][j] = d[1][j][j] = true;
      }
      vis.reset();
      for(int j = 1; j <= n; j++){
        if(!vis[j]){
          dfs(0, j);
        }
      }
      vis.reset();
      for(int j = 1; j <= n; j++){
        if(!vis[j]){
          dfs(1, j);
        }
      }
      for(int j = 1; j <= n; j++){
        if(ans[j] == -1 && d[0][j].count() + d[1][j].count() == n + 1){
          ans[j] = i;
        }
      }
    }
    for(int i = 1; i <= n; i++){
      cout << ans[i] << " ";
    }
  }
}
namespace sub4{
  const int lim = 2e5 + 5;
  int ans[lim];
  vector<int>topo, g[lim];
  void play(){
    for(int i = 1; i <= n; i++){
      g[i].clear();
    }
    for(int i = 1; i <= m; i++){
      g[x[i]].push_back(i);
    }
    if(topo.empty()){
      vector<int>in_deg(n + 1, 0);
      for(int i = 1; i <= m; i++){
        in_deg[y[i]]++;
      }
      queue<int>q;
      for(int i = 1; i <= n; i++){
        if(in_deg[i] == 0){
          q.push(i);
        }
      }
      while(!q.empty()){
        int u = q.front();
        q.pop();
        topo.push_back(u);
        for(int& i : g[u]){
          if(--in_deg[y[i]] == 0){
            q.push(y[i]);
          }
        }
      }
    }
    else{
      reverse(topo.begin(), topo.end());
    }
    set<int>s;
    vector<int>eid(n + 1, -1);
    for(int i = n - 1; i > -1; i--){
      for(int& j : g[topo[i]]){
        if(eid[y[j]] == -1){
          s.insert(eid[y[j]] = j);
        }
        else if(eid[y[j]] > j){
          s.erase(eid[y[j]]);
          s.insert(eid[y[j]] = j);
        } 
      }
      if(s.size() != n - i - 1){
        ans[topo[i]] = -1;
      }
      else if(!s.empty() && ans[topo[i]] != -1){
        maximize(ans[topo[i]], *s.rbegin());
      }
    }
  }
  void solve(){
    memset(ans, 0, sizeof(ans));
    play();
    for(int i = 1; i <= m; i++){
      swap(x[i], y[i]);
    }
    play();
    for(int i = 1; i <= n; i++){
      cout << ans[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;
  for(int i = 1; i <= m; i++){
    cin >> x[i] >> y[i];
  }
  if(n <= 1000 && m <= 4000){
    sub123::solve();
  }
  else{
    sub4::solve();
  }
}

Compilation message (stderr)

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

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 10 / 10
• Subtask 4: 68 / 68