oj.uz

Submission #1075829

# Submission time Handle Problem Language Result Execution time Memory
1075829 2024-08-26T09:22:31 Z edogawa_something Simurgh (IOI17_simurgh) C++17
0 / 100
 7 ms 12380 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll M=250000;
vector<pii> adj[M];
bool vis[M];
vii sp;
void dfs(ll x) {
  vis[x]=1;
  for(auto it:adj[x]) {
    if(vis[it.F])
      continue;
    else {
      sp.pb(it.S);
      dfs(it.F);
    }
  }
}
struct dsu {
  ll sz[250],pa[250];
  void init(ll x) {
    for(int i=0;i<x;i++)
      sz[i]=1,pa[i]=i;
  }
  ll get(ll x) {
    if(x==pa[x])
      return x;
    return pa[x]=get(pa[x]);
  }
  void unite(ll x,ll y) {
    x=get(x),y=get(y);
    if(x==y)
      return;
    if(sz[x]>sz[y])
      swap(x,y);
    pa[x]=y;
    sz[y]+=sz[x];
  }
  bool same(ll x,ll y) {
    return get(x)==get(y);
  }
}d;
ll cnt[M],cc[M];
bool a[M];
set<ll>s;
vector<int> find_roads(int n, std::vector<int> u, std::vector<int> vv) {
  for(int i=0;i<u.size();i++)
    adj[u[i]].pb({vv[i],i}),adj[vv[i]].pb({u[i],i});
  dfs(0);
  vector<int>ans,res;
  for(int i=0;i<u.size();i++)
    vis[i]=0;
  ll cc=0;
  for(auto it:sp) {
    s.clear();
    ans.clear();
    d.init(n);
    vii v;
    for(auto itt:sp) {
      if(itt!=it)
        ans.pb(itt),d.unite(u[itt],vv[itt]);
    }
    for(int i=0;i<u.size();i++)
      cnt[i]=0;
    for(int i=0;i<u.size();i++) {
      if(!d.same(u[i],vv[i])) {
        ans.pb(i);
        ll x=count_common_roads(ans);
        cc++;
        cnt[ans.back()]=x;
        s.insert(x);
        v.pb(i);
        vis[i]=1;
        ans.pop_back();
      }
    }
    if(s.size()==1) {
      bool cc[2];
      cc[0]=cc[1]=0;
      for(int i=0;i<u.size();i++) {
        if(!d.same(u[i],vv[i])&&vis[i]&&!cc[a[i]]) {
          cc[a[i]]=1;
          ans.pb(i);
          s.insert(count_common_roads(ans));
          ans.pop_back();
        }
      }
    }
    else {
      for(auto it:v) {
        if(cnt[it]==*s.rbegin()) {
          a[it]=1;
        }
      }
    }
  }
  for(int i=0;i<u.size();i++)
    if(a[i])res.pb(i);
  assert(res.size()==n-1);
  assert(cc<=30000);
  return res;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=0;i<u.size();i++)
      |               ~^~~~~~~~~
simurgh.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i=0;i<u.size();i++)
      |               ~^~~~~~~~~
simurgh.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<u.size();i++)
      |                 ~^~~~~~~~~
simurgh.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<u.size();i++) {
      |                 ~^~~~~~~~~
simurgh.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |       for(int i=0;i<u.size();i++) {
      |                   ~^~~~~~~~~
simurgh.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i=0;i<u.size();i++)
      |               ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp:106:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |   assert(res.size()==n-1);
      |          ~~~~~~~~~~^~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB correct
2 Correct 3 ms 6236 KB correct
3 Correct 2 ms 6236 KB correct
4 Correct 2 ms 6320 KB correct
5 Correct 2 ms 6236 KB correct
6 Runtime error 6 ms 12380 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB correct
2 Correct 3 ms 6236 KB correct
3 Correct 2 ms 6236 KB correct
4 Correct 2 ms 6320 KB correct
5 Correct 2 ms 6236 KB correct
6 Runtime error 6 ms 12380 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB correct
2 Correct 3 ms 6236 KB correct
3 Correct 2 ms 6236 KB correct
4 Correct 2 ms 6320 KB correct
5 Correct 2 ms 6236 KB correct
6 Runtime error 6 ms 12380 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 12380 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6236 KB correct
2 Correct 3 ms 6236 KB correct
3 Correct 2 ms 6236 KB correct
4 Correct 2 ms 6320 KB correct
5 Correct 2 ms 6236 KB correct
6 Runtime error 6 ms 12380 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -