oj.uz

답안 #586499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586499 2022-06-30T10:51:16 Z wdjpng 통행료 (IOI18_highway) C++17
12 / 100
 244 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>

#define int long long
#define all(a) a.begin(), a.end()
#define rep(i,n) for(int i = 0; i<n; i++)

using namespace std;

int k,m;

struct edge
{
  int w, i;
};

int N=90000, c1=0, c2=0;
vector<vector<edge>>E;
vector<int>p(N);
vector<int>ped(N,-1);
vector<int>pre(N,-1);
vector<int>post(N,-1);
vector<int>dep(N,0);
vector<vector<int>>up(N,vector<int>(18,0));

vector<int> dfs(int v, int par)
{
  if(par==-1) up[v][0]=v;
  p[v]=par;
  vector<int>cr;
  if(E[v].size()==1) cr.push_back(v);
  for(auto [w,i] : E[v]) if(w!=par) 
  {
    dep[w]=dep[v]+1;
    vector<int> ans = dfs(w,v);
    ped[w]=i;
    if(ans.size()>cr.size()) swap(cr,ans);
    for(int x : ans) cr.push_back(x);
    up[w][0]=v;
  }
  return cr;
}

void act(int to, int v, int c, int lim, vector<signed>&w)
{
  if(v==to||ped[v]==-1||w[ped[v]]||c==lim) return;
  w[ped[v]]=true;
  act(to,p[v],c+1, lim, w);
}


void findr(int v, int A, int B)
{
  vector<int>leaves=dfs(v,-1);
  for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];

  int start = 0, end = leaves.size();
  while (end-start>1)
  {
    vector<signed>w(m,0);
    int cur = (start+end)/2;
    for(int i = cur; i < leaves.size(); i++)
    {
      act(v,leaves[i],0,1e8,w);
    }

    if(k*B==ask(w)) start=cur;
    else end=cur;
  }

  int cle=leaves[start];
  for(int j = 17; j >= 0; j--) 
  {
    vector<signed>w(m,0);
    act(v, up[cle][j],0,1e8,w);
    if(ask(w)==k*B) cle=up[cle][j];
  }

  answer(0,cle);
}

void find_pair(signed n, std::vector<signed> U, std::vector<signed> V, signed A, signed B) {
  E.assign(n, vector<edge>());
  m = U.size();
  rep(i,m)
  {
    E[U[i]].push_back({V[i],i});
    E[V[i]].push_back({U[i],i});
  }
  vector<signed>tmp(m,0);
  k=ask(tmp)/A;

  findr(0,A,B);
}

Compilation message

highway.cpp: In function 'void findr(long long int, long long int, long long int)':
highway.cpp:6:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i,n) for(int i = 0; i<n; i++)
......
   55 |   for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];
      |                                   ~~~~~~~~~~
highway.cpp:55:31: note: in expansion of macro 'rep'
   55 |   for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];
      |                               ^~~
highway.cpp:62:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = cur; i < leaves.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19920 KB Output is correct
2 Correct 13 ms 19996 KB Output is correct
3 Correct 12 ms 20048 KB Output is correct
4 Correct 12 ms 20012 KB Output is correct
5 Correct 12 ms 19964 KB Output is correct
6 Correct 12 ms 20048 KB Output is correct
7 Correct 12 ms 20048 KB Output is correct
8 Correct 12 ms 19992 KB Output is correct
9 Correct 14 ms 20048 KB Output is correct
10 Correct 13 ms 20056 KB Output is correct
11 Correct 17 ms 19928 KB Output is correct
12 Correct 13 ms 20024 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 20140 KB Output is correct
2 Correct 26 ms 21252 KB Output is correct
3 Correct 150 ms 29464 KB Output is correct
4 Correct 178 ms 29456 KB Output is correct
5 Correct 174 ms 29404 KB Output is correct
6 Correct 184 ms 29524 KB Output is correct
7 Correct 180 ms 29360 KB Output is correct
8 Correct 193 ms 29548 KB Output is correct
9 Correct 178 ms 29448 KB Output is correct
10 Correct 190 ms 29416 KB Output is correct
11 Correct 202 ms 32196 KB Output is correct
12 Correct 206 ms 33508 KB Output is correct
13 Correct 168 ms 32404 KB Output is correct
14 Correct 194 ms 31180 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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