oj.uz

Submission #1076429

# Submission time Handle Problem Language Result Execution time Memory
1076429 2024-08-26T13:48:25 Z edogawa_something Simurgh (IOI17_simurgh) C++17
19 / 100
 83 ms 15188 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;
vii adj[M];
bool vis[M];
vector<int>ans;
ll n,cntt,root;
ll label[500][500],deg[M];
bool viss[M];
bool visss[M];
void dfs(ll x) {
  vis[x]=1;
  vii vv;
  vector<int>v;
  for(int i=0;i<n;i++) {
    if(vis[i])
      continue;
    vv.pb(i);
  }
  while(vv.size()) {
    ll l=0,r=vv.size()-1,mid,res=-1;
    while(l<=r) {
      for(int i=0;i<n;i++)
        viss[i]=0;
      v=ans;
      mid=((l+r)>>1);
      for(int i=r;i>=mid;i--) {
        v.pb(label[vv[i]][x]);
        viss[vv[i]]=1;
      }
      for(int i=0;i<n;i++) {
        if(!(vis[i]||viss[i]||visss[i])) {
          v.pb(label[root][i]);
        }
      }
      ll x=count_common_roads(v);
      if(x==cntt) {
        r=mid-1;
      }
      else
        l=mid+1,res=mid;
    }
    if(res==-1)
      break;
    adj[x].pb(vv[res]);
    vis[vv[res]]=1;
    visss[vv[res]]=1;
    ans.pb(label[x][vv[res]]);
    cntt++;
    while(vv.size()>=res+1)
      vv.pop_back();
  }
  for(auto it:adj[x])
    dfs(it);
}
set<ll>s;
ll cnt[M];
vector<int> find_roads(int N, std::vector<int> u, std::vector<int> vv) {
  n=N;
  if(n==2)
    return {0};
  for(int i=0;i<u.size();i++)
    label[u[i]][vv[i]]=label[vv[i]][u[i]]=i;
  for(int i=0;i<n;i++) {
    vector<int>v;
    for(int j=0;j<n;j++) {
      if(j==i)
        continue;
      v.pb(label[i][j]);
    }
    deg[i]=count_common_roads(v);
  }
  for(int i=0;i<n;i++) {
    if(deg[i]==1) {
      root=i;
    }
  }
  vector<int>v;
  for(int i=0;i<n;i++) {
    if(i!=root) {
      for(int j=0;j<n;j++) {
        if(j!=root&&j!=i)
          v.pb(label[i][j]);
      }
      break;
    }
  }
  for(int i=0;i<n;i++) {
    if(i==root)
      continue;
    v.pb(label[i][root]);
    ll x=count_common_roads(v);
    cnt[label[i][root]]=x;
    s.insert(x);
    v.pop_back();
  }
  for(int i=0;i<n;i++) {
    if(i==root)
      continue;
    if(cnt[label[i][root]]==*s.rbegin()) {
      adj[root].pb(i);
      break;
    }
  }
  memset(vis,0,sizeof vis);
  ans.pb(label[adj[root][0]][root]);
  vis[root]=1;
  cntt=1;
  dfs(adj[root][0]);
  return ans;
}
/*
5 10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
3 6 8 9

*/

Compilation message

simurgh.cpp: In function 'void dfs(ll)':
simurgh.cpp:58:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   58 |     while(vv.size()>=res+1)
      |           ~~~~~~~~~^~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:70:16: 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++)
      |               ~^~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB correct
2 Correct 3 ms 6492 KB correct
3 Correct 3 ms 6492 KB correct
4 Incorrect 3 ms 6236 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB correct
2 Correct 3 ms 6492 KB correct
3 Correct 3 ms 6492 KB correct
4 Incorrect 3 ms 6236 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB correct
2 Correct 3 ms 6492 KB correct
3 Correct 3 ms 6492 KB correct
4 Incorrect 3 ms 6236 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB correct
2 Correct 3 ms 6488 KB correct
3 Correct 47 ms 10576 KB correct
4 Correct 67 ms 12228 KB correct
5 Correct 69 ms 12628 KB correct
6 Correct 51 ms 12112 KB correct
7 Correct 50 ms 12124 KB correct
8 Correct 48 ms 12220 KB correct
9 Correct 70 ms 12112 KB correct
10 Correct 71 ms 14316 KB correct
11 Correct 83 ms 12368 KB correct
12 Correct 72 ms 15188 KB correct
13 Correct 3 ms 6488 KB correct
14 Correct 59 ms 12124 KB correct
15 Correct 69 ms 14932 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB correct
2 Correct 3 ms 6492 KB correct
3 Correct 3 ms 6492 KB correct
4 Incorrect 3 ms 6236 KB WA in grader: NO
5 Halted 0 ms 0 KB -