이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include "simurgh.h"
#define MAXN 507
#define MAXM 300007
using namespace std;
int n,m,dep[MAXN],edges;
vector< pair<int,int> > v[MAXN];
bool intree[MAXM],vis[MAXN];
pair<int,int> edge[MAXM],parent[MAXN];
int value[MAXM],st[MAXM],sumtree;
vector<int> ans;
unordered_set<int> s;
int questions;
int calc(vector<int> rem,vector<int> add){
questions++;
for(int i:rem)s.erase(i);
for(int i:add)s.insert(i);
vector<int> w;
for(int i:s){
w.push_back(i-1);
}
for(int i:rem)s.insert(i);
for(int i:add)s.erase(i);
return count_common_roads(w);
}
void dfs(int x){
vis[x]=true;
for(int i=0;i<v[x].size();i++){
if(vis[v[x][i].first])continue;
dep[v[x][i].first]=dep[x]+1;
parent[v[x][i].first]={x,v[x][i].second};
dfs(v[x][i].first);
intree[v[x][i].second]=true;
s.insert(v[x][i].second);
}
}
vector<int> path,toask;
int total;
void dfs2(int x){
vis[x]=true;
for(int i=0;i<v[x].size();i++){
if(vis[v[x][i].first] or !intree[v[x][i].second]){
continue;
}
toask.push_back(v[x][i].second-1);
total-=(value[v[x][i].second]-1);
dfs2(v[x][i].first);
}
}
void up(int x,int y){
if(x==y)return;
path.push_back(parent[x].second);
up(parent[x].first,y);
}
int howmany(int root,int l,int r){
toask.clear();
for(int i=1;i<=n;i++)vis[i]=false;
vis[root]=true;
for(int i=l;i<=r;i++)vis[v[root][i].first]=true;
for(int i=l;i<=r;i++){
toask.push_back(v[root][i].second-1);
}
total=0;
dfs2(root);
for(int i=l;i<=r;i++){
dfs2(v[root][i].first);
}
total+=count_common_roads(toask);
return total;
}
void solve(int root,int l,int r){
if(l==r){
value[v[root][l].second]=2;
return;
}
int mid=(l+r)/2;
if(howmany(root,l,mid)!=0){
solve(root,l,mid);
}
if(howmany(root,mid+1,r)!=0){
solve(root,mid+1,r);
}
}
vector<int> find_roads(int N,vector<int> from,vector<int> to){
n=N; m=int(from.size());
for(int i=1;i<=m;i++){
from[i-1]++; to[i-1]++;
edge[i]={from[i-1],to[i-1]};
v[from[i-1]].push_back({to[i-1],i});
v[to[i-1]].push_back({from[i-1],i});
}
dfs(1);
sumtree=calc({},{});
for(int i=1;i<=m;i++){
if(intree[i])continue;
int u=from[i-1],w=to[i-1];
if(dep[u]>dep[w])swap(u,w);
path.clear();
up(w,u);
int mins=sumtree,maxs=sumtree,br=0,ask=0;
for(int f:path){
if(value[f]==0){
st[f]=calc({f},{i});
br++;
mins=min(mins,st[f]);
maxs=max(maxs,st[f]);
}
}
if(br==0)continue;
if(mins==maxs){
for(int f:path){
if(value[f]==0)continue;
st[f]=calc({f},{i});
ask=value[f];
mins=min(mins,st[f]);
maxs=max(maxs,st[f]);
break;
}
}
if(ask==0)ask=1;
for(int f:path){
if(value[f]!=0)continue;
if(mins==maxs)value[f]=ask;
else{
if(st[f]==mins)value[f]=2;
else value[f]=1;
}
}
}
for(int i=1;i<=m;i++){
if(intree[i] and value[i]==0)value[i]=2;
}
for(int i=1;i<=n;i++){
solve(i,0,v[i].size()-1);
}
for(int i=1;i<=m;i++){
if(value[i]==2){
ans.push_back(i-1);
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
simurgh.cpp: In function 'void dfs2(int)':
simurgh.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |