제출 #1060023

#제출 시각아이디문제언어결과실행 시간메모리
1060023UnforgettableplSplit the Attractions (IOI19_split)C++17
18 / 100
2050 ms22724 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { vector<pair<int,int>> poss = {{a,1},{b,2},{c,3}}; sort(poss.begin(), poss.end()); vector<vector<int>> fulladj(n); for(int i=0;i<p.size();i++)fulladj[p[i]].emplace_back(q[i]); for(int i=0;i<p.size();i++)fulladj[q[i]].emplace_back(p[i]); pair<int,int> answer = {-1,-1}; for(int root=0;root<n;root++){ vector<vector<int>> adj(n); vector<bool> visited(n); function<void(int,int)> adjcreate = [&](int x,int p) { if(visited[x])return; if(p!=-1) { adj[p].emplace_back(x); adj[x].emplace_back(p); } visited[x]=true; for(int&i:fulladj[x])adjcreate(i,x); }; adjcreate(root,-1); bool reiter = false; back: function<int(int,int)> dfs = [&](int x,int p) { int subsize = 1; for(int&i:adj[x])if(i!=p)subsize+=dfs(i,x); if(subsize>=poss[0].first and n-subsize>=poss[1].first)answer={x,p}; return subsize; }; dfs(0,-1); if(answer.first==-1) { if(reiter) { swap(poss[1],poss[0]); continue; } reiter = true; swap(poss[1],poss[0]); goto back; } { vector<int> res(n,2); int curr = 0; int currnode = 0; int tar = 0; function<void(int,int)> dfs = [&](int x,int p) { if(curr==tar)return; res[x]=currnode; curr++; for(int&i:adj[x])if(i!=p)dfs(i,x); }; curr = 0; currnode = 0; tar = poss[0].first; dfs(answer.first,answer.second); curr = 0; currnode = 1; tar = poss[1].first; dfs(answer.second,answer.first); for(int&i:res)i=poss[i].second; return res; } } return vector<int>(n); }

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:9:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for(int i=0;i<p.size();i++)fulladj[p[i]].emplace_back(q[i]);
      |              ~^~~~~~~~~
split.cpp:10:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i=0;i<p.size();i++)fulladj[q[i]].emplace_back(p[i]);
      |              ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...