제출 #409321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409321		MKopchev	통행료 (IOI18_highway)	C++14	100 / 100	315 ms	17716 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
/*
namespace {

constexpr int MAX_NUM_CALLS = 100;
constexpr long long INF = 1LL << 61;

int N, M, A, B, S, T;
std::vector<int> U, V;
std::vector<std::vector<std::pair<int, int>>> graph;

bool answered, wrong_pair;
int num_calls;

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

void wrong_answer(const char *MSG) {
  printf("Wrong Answer: %s\n", MSG);
  exit(0);
}

}  // namespace

long long ask(const std::vector<int> &w) {
  if (++num_calls > MAX_NUM_CALLS) {
    wrong_answer("more than 100 calls to ask");
  }
  if (w.size() != (size_t)M) {
    wrong_answer("w is invalid");
  }
  for (size_t i = 0; i < w.size(); ++i) {
    if (!(w[i] == 0 || w[i] == 1)) {
      wrong_answer("w is invalid");
    }
  }

  std::vector<bool> visited(N, false);
  std::vector<long long> current_dist(N, INF);
  std::queue<int> qa, qb;
  qa.push(S);
  current_dist[S] = 0;
  while (!qa.empty() || !qb.empty()) {
    int v;
    if (qb.empty() ||
        (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
      v = qa.front();
      qa.pop();
    } else {
      v = qb.front();
      qb.pop();
    }
    if (visited[v]) {
      continue;
    }
    visited[v] = true;
    long long d = current_dist[v];
    if (v == T) {
      return d;
    }
    for (auto e : graph[v]) {
      int vv = e.first;
      int ei = e.second;
      if (!visited[vv]) {
        if (w[ei] == 0) {
          if (current_dist[vv] > d + A) {
            current_dist[vv] = d + A;
            qa.push(vv);
          }
        } else {
          if (current_dist[vv] > d + B) {
            current_dist[vv] = d + B;
            qb.push(vv);
          }
        }
      }
    }
  }
  return -1;
}

void answer(int s, int t) {
  if (answered) {
    wrong_answer("answered not exactly once");
  }

  if (!((s == S && t == T) || (s == T && t == S))) {
    wrong_pair = true;
  }

  answered = true;
}
*/
const int nmax=1e5+42;

vector< pair<int,int> > adj[nmax];

int n,m,a,b;

vector<int> idle;

long long mem_d;

int dist[nmax][2];

queue<int> q;

vector<int> mem_U,mem_V;

int solve(int from,int id,vector<int> valid_edges,vector<int> blocked)
{
    //cout<<"solve "<<from<<" "<<id<<" "<<valid_edges.size()<<endl;

    set<int> in={};
    for(auto w:valid_edges)in.insert(w);

    int was=valid_edges.size();

    for(auto w:valid_edges)
    {
        int p=mem_U[w];
        int q=mem_V[w];

        if(dist[p][id]>dist[q][id])swap(p,q);
    }

    /*
    for(int i=0;i<mem_U.size();i++)
        if(in.count(i)==0)valid_edges.push_back(i);
    */

    //for(auto w:valid_edges)cout<<dist[mem_U[w]]<<" "<<dist[mem_V[w]]<<endl;

    int ok=was-1,not_ok=-2;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        vector<int> cur=idle;

        for(int j=av+1;j<valid_edges.size();j++)
            cur[valid_edges[j]]=1;

        for(auto w:blocked)cur[w]=1;

        if(ask(cur)==mem_d)ok=av;
        else not_ok=av;
    }

    //cout<<"valid= ";for(auto w:valid_edges)cout<<w<<" -> "<<mem_U[w]<<" "<<mem_V[w]<<" , ";cout<<endl;

    //cout<<"ok= "<<ok<<endl;

    //system("pause");
    //exit(0);

    if(ok==-1)return from;

    int u=mem_U[valid_edges[ok]];
    int v=mem_V[valid_edges[ok]];

    //cout<<"dist= "<<dist[u][id]<<" "<<dist[v][id]<<endl;

    //cout<<"u= "<<u<<" v= "<<v<<endl;

    if(dist[u][id]<dist[v][id])return v;
    return u;
}

int dist_help[nmax][2];

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(int i=0;i<m;i++)idle.push_back(0);

    for(int i=0;i<m;i++)
    {
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }

    mem_U=U;
    mem_V=V;

    mem_d=ask(idle);

    //cout<<"d= "<<mem_d/A<<endl;

    int ok=m-1,not_ok=-1;

    while(ok-not_ok>1)
    {
        int av=(ok+not_ok)/2;

        vector<int> me=idle;
        for(int j=0;j<=av;j++)me[j]=1;

        if(ask(me)>mem_d)ok=av;
        else not_ok=av;
    }

    //cout<<"edge "<<U[ok]<<" "<<V[ok]<<endl;

    /*
    q.push(from);

    set<int> in={};

    while(q.size())
    {
        dist[from]=0;

        int node=q.front();

        q.pop();

        for(auto w:adj[node])
            if(dist[w.first]==-1)
            {
                dist[w.first]=dist[node]+1;

                valid_edges.push_back(w.second);
                in.insert(w.second);

                q.push(w.first);
            }
    }
    */

    memset(dist,-1,sizeof(dist));

    int outp[2];

    for(int which=0;which<2;which++)
    {
        vector<int> valid_edges={};

        int from=(which==0?U[ok]:V[ok]);

        dist[from][which]=0;

        q.push(from);

        //cout<<which<<" "<<from<<endl;

        while(q.size())
        {

        int node=q.front();

        //cout<<"node= "<<node<<endl;

        q.pop();

        for(auto w:adj[node])
            if(dist[w.first][which]==-1)
            {
                dist[w.first][which]=dist[node][which]+1;

                //valid_edges.push_back(w.second);

                q.push(w.first);
            }
        }
        //outp[which]=solve(from,valid_edges);
    }

    memset(dist_help,-1,sizeof(dist_help));

    for(int which=0;which<2;which++)
    {
        vector<int> valid_edges={};

        int from=(which==0?U[ok]:V[ok]);

        dist_help[from][which]=0;

        q.push(from);

        //cout<<which<<" "<<from<<endl;

        vector<int> blocked={};

        while(q.size())
        {

        int node=q.front();

        q.pop();



        for(auto w:adj[node])
            if(dist[w.first][which]<dist[w.first][!which])
                {
                    if(dist_help[w.first][which]==-1)
                    {
                        dist_help[w.first][which]=dist_help[node][which]+1;

                        valid_edges.push_back(w.second);

                        q.push(w.first);
                    }
                    else if(dist_help[w.first][which]==dist_help[node][which]+1)blocked.push_back(w.second);

            }
            else if(w.second!=ok)blocked.push_back(w.second);
        }

        /*
        for(int i=0;i<n;i++)
            for(auto j:adj[i])
                if(i<j.first&&dist[i][which]==dist[j.first][which])blocked.push_back(j.second);
        */

        outp[which]=solve(from,which,valid_edges,blocked);
    }

    int s=outp[0];
    int t=outp[1];

    //cout<<"s= "<<s<<" t= "<<t<<endl;

    answer(s,t);
}
/*
int main() {
  N = read_int();
  M = read_int();
  A = read_int();
  B = read_int();
  S = read_int();
  T = read_int();
  U.resize(M);
  V.resize(M);
  graph.assign(N, std::vector<std::pair<int, int>>());
  for (int i = 0; i < M; ++i) {
    U[i] = read_int();
    V[i] = read_int();
    graph[U[i]].push_back({V[i], i});
    graph[V[i]].push_back({U[i], i});
  }

  answered = false;
  wrong_pair = false;
  num_calls = 0;
  find_pair(N, U, V, A, B);
  if (!answered) {
    wrong_answer("answered not exactly once");
  }
  if (wrong_pair) {
    wrong_answer("{s, t} is wrong");
  }
  printf("Accepted: %d\n", num_calls);
  return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'int solve(int, int, std::vector<int>, std::vector<int>)':
highway.cpp:150:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for(int j=av+1;j<valid_edges.size();j++)
      |                        ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31