# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1100242 | MMihalev | Simurgh (IOI17_simurgh) | C++14 | 66 ms | 4180 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
#include<set>
#include<queue>
#include "simurgh.h"
using namespace std;
const int MAX_N=5e2+3;
const int MAX_M=125000;
int n,m;
int q;
vector<int>edges;
vector<pair<int,int>>g[MAX_N];
bool used[MAX_N];
vector<int>comp;
vector<vector<int>>comps;
int adj[MAX_N];
bool stat[MAX_M];
bool checked[MAX_N];
int forsure;
void reset()
{
comps.clear();
edges.clear();
for(int i=0;i<n;i++)
{
adj[i]=-1;
used[i]=0;
}
}
void dfs(int u)
{
if(adj[u]!=-1)
{
if(!checked[adj[u]])comp.push_back(adj[u]);
if(stat[adj[u]])forsure=adj[u];
}
used[u]=1;
for(auto [v,edge]:g[u])
{
if(used[v])continue;
edges.push_back(edge);
dfs(v);
}
}
void rep(int prev,int edge)
{
for(int i=0;i<edges.size();i++)
{
if(edges[i]==prev){edges[i]=edge;return;}
}
while(1);
}
vector<int> find_roads(int N, vector<int> u, vector<int> v)
{
n=N;
m=u.size();
vector<int>ans;
for(int i=0;i<m;i++)
{
g[u[i]].push_back({v[i],i});
g[v[i]].push_back({u[i],i});
}
for(int u=0;u<n;u++)
{
reset();
used[u]=1;
for(auto [v,edge]:g[u])
{
adj[v]=edge;
}
for(auto [v,edge]:g[u])
{
if(!used[v])
{
forsure=-1;
comp.clear();
dfs(v);
if(forsure!=-1)
{
comp.push_back(forsure);
}
comps.push_back(comp);
}
}
for(auto c:comps)
{
edges.push_back(c[0]);
}
for(auto c:comps)
{
if(q==30000)while(1);
if(edges.size()!=n-1)while(1);
int ma=count_common_roads(edges);q++;
vector<int>marked;
marked.push_back(c[0]);
int prev=c[0];
for(int edge:c)
{
if(edge==c[0])continue;
rep(prev,edge);
if(edges.size()!=n-1)while(1);
if(q==30000)while(1);
int cur=count_common_roads(edges);q++;
if(cur>ma)
{
marked.clear();
ma=cur;
marked.push_back(edge);
}
else if(cur==ma)
{
marked.push_back(edge);
}
prev=edge;
}
for(int edge:marked)stat[edge]=1;
}
for(auto [v,edge]:g[u])checked[edge]=1;
}
for(int i=0;i<m;i++)
{
if(stat[i])ans.push_back(i);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |