| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 393569 |
2021-04-24T03:45:03 Z |
tinjyu |
Simurgh (IOI17_simurgh) |
C++14 |
|
1 ms |
332 KB |
#include "simurgh.h"
#include <iostream>
#include <vector>
using namespace std;
long long int val[100005],n,road[100005],map[1000005][2],m,cnt,tagv[1000005],tage[1000005],deg[100005],used[100005];
vector<int> r,r1;
int add(int a,int b)
{
map[cnt][0]=b;
map[cnt][1]=road[a];
road[a]=cnt;
cnt++;
map[cnt][0]=a;
map[cnt][1]=road[b];
road[b]=cnt;
cnt++;
return 0;
}
long long int dfs(int x,int y)
{
//cout<<x<<endl;
tagv[x]=1;
long long int g=road[x];
while(g!=-1)
{
long long int now=map[g][0];
//cout<<x<<" "<<now<<" "<<g<<endl;
if(used[g/2]==0 && tagv[now]==0 && tage[g/2]==0)
{
used[g/2]=1;
if(now==y)
{
r.push_back(g/2);
return 0;
}
int tmp=dfs(now,y);
if(tmp==0)
{
r.push_back(g/2);
return 0;
}
used[g/2]=0;
}
g=map[g][1];
}
while(g!=-1)
{
long long int now=map[g][0];
//cout<<x<<" "<<now<<" "<<g<<endl;
if(used[g/2]==0 && tagv[now]==0 && tage[g/2]==1)
{
used[g/2]=1;
if(now==y)
{
r.push_back(g/2);
return 0;
}
int tmp=dfs(now,y);
if(tmp==0)
{
r.push_back(g/2);
return 0;
}
used[g/2]=0;
}
g=map[g][1];
}
return 1;
}
int dfs1(int x)
{
tagv[x]=1;
long long int g=road[x];
while(g!=-1)
{
long long int now=map[g][0];
if(tagv[now]==0)
{
r1.push_back(g/2);
dfs1(now);
}
g=map[g][1];
}
return 0;
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
n=N;
for(int i=0;i<n;i++)road[i]=-1;
m=u.size();
for(int i=0;i<m;i++)
{
add(u[i],v[i]);
//cout<<u[i]<<" "<<v[i]<<" "<<map[i*2][0]<<" "<<map[i*2+1][0]<<endl;
}
vector<int> ans;
vector<int> ask;
for(int t=0;t<n;t++)
{
//cout<<i<<endl;
long long int g=road[t];
while(g!=-1)
{
long long int now=map[g][0];
if(tage[g/2]==0)
{
for(int j=0;j<m;j++)used[j]=0;
//cout<<t<<" "<<g/2<<endl;
for(int j=0;j<n;j++)
{
tagv[j]=0;
}
r.clear();
r1.clear();
ask.clear();
used[g/2]=1;
long long int tmp=dfs(now,t);
//for(int i=0;i<r.size();i++)cout<<r[i]<<" ";
//cout<<endl;
if(r.size()==0)
{
ans.push_back(g/2);
tage[g/2]=1;
}
else
{
r.push_back(g/2);
for(int i=0;i<n;i++)tagv[i]=0;
for(int i=0;i<r.size();i++)
{
//cout<<r[i]<<" "<<u[r[i]]<<" "<<v[r[i]]<<endl;
tagv[u[r[i]]]=1;
tagv[v[r[i]]]=1;
}
for(int i=0;i<r.size();i++)
{
dfs1(u[r[i]]);
//cout<<"ok"<<endl;
dfs1(v[r[i]]);
}
long long int mi=9999999;
long long int c=0;
for(int i=0;i<r.size();i++)
{
ask.clear();
for(int j=0;j<r.size();j++)
{
if(i==j)continue;
ask.push_back(r[j]);
}
for(int j=0;j<r1.size();j++)
{
ask.push_back(r1[j]);
}
//cout<<"ask"<<endl;
//for(int j=0;j<ask.size();j++)cout<<ask[j]<<" ";
//cout<<endl;
val[i]=count_common_roads(ask);
//cout<<val[i]<<endl;0
mi=min(mi,val[i]);
}
for(int i=0;i<r.size();i++)
{
if(val[i]!=mi)c=1;
}
if(c==1)
{
for(int i=0;i<r.size();i++)
{
if(val[i]==mi)
{
if(tage[r[i]]==0)ans.push_back(r[i]);
}
}
}
for(int i=0;i<r.size();i++)tage[r[i]]=1;
}
}
g=map[g][1];
}
}
//cout<<"ans"<<endl;
//for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
//cout<<endl;
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<r.size();i++)
| ~^~~~~~~~~
simurgh.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i=0;i<r.size();i++)
| ~^~~~~~~~~
simurgh.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int i=0;i<r.size();i++)
| ~^~~~~~~~~
simurgh.cpp:145:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int j=0;j<r.size();j++)
| ~^~~~~~~~~
simurgh.cpp:150:20: 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=0;j<r1.size();j++)
| ~^~~~~~~~~~
simurgh.cpp:161:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int i=0;i<r.size();i++)
| ~^~~~~~~~~
simurgh.cpp:167:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int i=0;i<r.size();i++)
| ~^~~~~~~~~
simurgh.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for(int i=0;i<r.size();i++)tage[r[i]]=1;
| ~^~~~~~~~~
simurgh.cpp:116:19: warning: unused variable 'tmp' [-Wunused-variable]
116 | long long int tmp=dfs(now,t);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Correct |
1 ms |
332 KB |
correct |
| 3 |
Correct |
1 ms |
332 KB |
correct |
| 4 |
Correct |
1 ms |
332 KB |
correct |
| 5 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 6 |
Halted |
0 ms |
0 KB |
- |
