oj.uz

답안 #1032868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032868 2024-07-24T10:10:23 Z amirhoseinfar1385 통행료 (IOI18_highway) C++17
0 / 100
 10 ms 5976 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=90000+10;
long long n,a,b,aval,s,t;
long long m,sz[maxn],vis[maxn];
vector<long long>adj[maxn];

struct yal{
  long long u,v;
  long long getad(long long fu){
    return (fu^v^u);
  }
}alle[maxn];

long long pors(vector<long long>er){
  vector<int>ret(m);
  for(auto x:er){
    ret[x]=1;
  }
  return ask(ret);
}

void calsz(long long u,long long par=-1){
  sz[u]=1;
  for(auto x:adj[u]){
    long long v=alle[x].getad(u);
    if(vis[v]==0&&v!=par){
      calsz(v,u);
      sz[u]+=sz[v];
    }
  }
}

long long findcen(long long u,long long szz,long long par=-1){
  for(auto x:adj[u]){
    long long v=alle[x].getad(u);
    if(vis[v]==0&&sz[v]*2>szz&&v!=par){
      return findcen(v,szz,u);
    }
  }
  return u;
}
vector<long long>ersa;
int f=0;
int had=0;

void go(int u,int par=-1){
  if(u==had){
    f=1;
  }
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(v==par||vis[v]){
      continue;
    }
    ersa.push_back(x);
    go(v,u);
  }
}
int nago=0;

long long finds(long long u=0){
 // cout<<u<<endl;
  calsz(u);
 // cout<<u<<endl;
  long long v=findcen(u,sz[u]);
 // cout<<u<<endl;
  vector<long long>tof;
  ersa.clear();
  for(auto x:adj[v]){
    long long z=alle[x].getad(v);
    if(vis[z]==0){
      tof.push_back(x);
      ersa.push_back(tof.back());
      go(alle[tof.back()].getad(v),v);
    }
  }
  long long fake=pors(tof);
  if(fake==aval&&nago==1){
    vis[v]=1;
    return finds(u);
  }
  if(fake-b+a==aval){
    return v;
  }
  nago=1;
  long long low=-1,high=(long long)tof.size()-1,mid;
  for(int i=0;i<(int)tof.size();i++){
    f=0;
    had=u;
    go(alle[tof[i]].getad(v),v);
    if(f){
      vector<long long>hey;
      for(int j=0;j<(int)tof.size();j++){
        if(j==i){
          continue;
        }
        hey.push_back(tof[j]);
      }
      tof=hey;
      break;
    } 
  }
  while(high-low>1){
    mid=(high+low)>>1;
    ersa.clear();
    for(long long i=0;i<=mid;i++){
      ersa.push_back(tof[i]);
      go(alle[tof[i]].getad(v),v);
    }
    fake=pors(ersa);
    if(fake==aval){
      low=mid;
    }else{
      high=mid;
    }
  }
//  cout<<u<<" "<<v<<endl;
  vis[v]=1;
  return finds(alle[tof[high]].getad(v));
}
vector<long long>ham;
long long bal[maxn];

void dfscal(long long u,long long len,long long par=-1,long long now=0){
  if(now==len){
    ham.push_back(u);
    return ;
  }
  for(auto x:adj[u]){
    long long v=alle[x].getad(u);
    if(v==par){
      continue;
    }
    bal[v]=x;
    dfscal(v,len,u,now+1);
  }
}

long long findt(){
  dfscal(s,aval/a);
  long long low=-1,high=(long long)ham.size()-1,mid;
  while(high-low>1){
    vector<long long>ers;
    mid=(high+low)>>1;
    for(long long i=0;i<=mid;i++){
      ers.push_back(bal[ham[i]]);
    }
    long long fake=pors(ers);
    if(fake==aval){
      low=mid;
    }else{
      high=mid;
    }
  }
  return ham[high];
}

void calc(){
 // cout<<"av"<<endl;
  s=finds();
  //s=0;
 // cout<<"dov"<<endl;
  t=findt();
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  n=N;
  m = U.size();
  a=A;
  b=B;
 for(long long i=0;i<m;i++){
  alle[i].u=U[i];
  alle[i].v=V[i];
  adj[U[i]].push_back(i);
  adj[V[i]].push_back(i);
 }
 if(m!=n-1){
  answer(0,1);
  return ;
 }
 aval=pors({});
 calc();
  //cout<<s<<" "<<t<<endl;
  answer(s,t);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 4440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4660 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 5976 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4952 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 4952 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -