제출 #964813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964813		AdamGS	Simurgh (IOI17_simurgh)	C++17	70 / 100	288 ms	8692 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=507;
vector<pair<int,int>>V[LIM];
vector<int>D;
pair<int,int>kraw[LIM*LIM];
int pre[LIM], mi[LIM], oc[LIM], jaki[LIM], drzewo[LIM*LIM], typ[LIM*LIM], F[LIM], lpre, n, m;
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
  if(fnd(a)==fnd(b)) return false;
  F[fnd(a)]=fnd(b);
  return true;
}
void DFS(int x, int o) {
  pre[x]=mi[x]=++lpre;
  for(auto i : V[x]) if(i.st!=o) {
    if(!pre[i.st]) {
      oc[i.st]=x;
      jaki[i.st]=i.nd;
      drzewo[i.nd]=1;
      DFS(i.st, x);
      mi[x]=min(mi[x], mi[i.st]);
    } else mi[x]=min(mi[x], pre[i.st]);
  }
  if(x && mi[x]==pre[x]) typ[jaki[x]]=1;
}
int cnt(vector<int>P) {
  rep(i, n) F[i]=i;
  for(auto i : P) uni(kraw[i].st, kraw[i].nd);
  int sum=0;
  for(auto i : D) if(uni(kraw[i].st, kraw[i].nd)) {
    sum+=typ[i];
    P.pb(i);
  }
  return count_common_roads(P)-sum;
}
void solve(vector<int>P, int k) {
  if(!k) {
    for(auto i : P) typ[i]=0;
    return;
  }
  if(P.size()==k) {
    for(auto i : P) typ[i]=1;
    return;
  }
  int sr=(P.size()+1)/2;
  vector<int>A, B;
  rep(i, sr) A.pb(P[i]);
  for(int i=sr; i<P.size(); ++i) B.pb(P[i]);
  int x=cnt(A);
  solve(A, x);
  solve(B, k-x);
}
vector<int>find_roads(int _n, vector<int>_u, vector<int>_v) {
  n=_n; m=_u.size();
  rep(i, m) {
    kraw[i]={_u[i], _v[i]};
    if(kraw[i].st>kraw[i].nd) swap(kraw[i].st, kraw[i].nd);
    V[kraw[i].st].pb({kraw[i].nd, i});
    V[kraw[i].nd].pb({kraw[i].st, i});
    typ[i]=-1;
  }
  DFS(0, 0);
  rep(i, m) if(drzewo[i]) D.pb(i);
  int x=count_common_roads(D);
  rep(i, m) if(!drzewo[i]) {
    int a=kraw[i].st, b=kraw[i].nd;
    if(pre[a]<pre[b]) swap(a, b);
    bool ok=false;
    for(int j=a; j!=b; j=oc[j]) {
      if(typ[jaki[j]]==-1) ok=true;
    }
    if(!ok) continue;
    for(int j=a; j!=b; j=oc[j]) if(typ[jaki[j]]==-1) {
      vector<int>T=D;
      rep(l, T.size()) if(T[l]==jaki[j]) T[l]=i;
      int y=count_common_roads(T);
      if(x==y) typ[jaki[j]]=typ[i];
      else if(x==y+1) {
        typ[jaki[j]]=1;
        typ[i]=0;
      } else {
        typ[jaki[j]]=0;
        typ[i]=1;
      }
    }
    if(typ[i]==-1) {
      ok=false;
      for(int j=a; j!=b; j=oc[j]) if(typ[jaki[j]]!=-1) {
        vector<int>T=D;
        rep(l, T.size()) if(T[l]==jaki[j]) T[l]=i;
        int y=count_common_roads(T);
        typ[i]=y-x+typ[jaki[j]];
        ok=true;
        break;
      }
      if(!ok) typ[i]=0;
    }
    for(int j=a; j!=b; j=oc[j]) if(typ[jaki[j]]==-1) typ[jaki[j]]=typ[i];
  }
  rep(i, n) {
    vector<int>P;
    rep(j, m) if(kraw[j].st==i || kraw[j].nd==i) P.pb(j);
    solve(P, cnt(P));
  }
  vector<int>ans;
  rep(i, m) if(typ[i]==1) ans.pb(i);
  return ans;
}

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

simurgh.cpp: In function 'void solve(std::vector<int>, int)':
simurgh.cpp:51:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   if(P.size()==k) {
      |      ~~~~~~~~^~~
simurgh.cpp:58:18: 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=sr; i<P.size(); ++i) B.pb(P[i]);
      |                 ~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
simurgh.cpp:85:7: note: in expansion of macro 'rep'
   85 |       rep(l, T.size()) if(T[l]==jaki[j]) T[l]=i;
      |       ^~~
simurgh.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
simurgh.cpp:100:9: note: in expansion of macro 'rep'
  100 |         rep(l, T.size()) if(T[l]==jaki[j]) T[l]=i;
      |         ^~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30