| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 590069 | LIF | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 272 ms | 28028 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int checkx[1005][1005];
int f[1005];
int find(int x)
{
if(f[x] == x)
{
return x;
}
return f[x] = find(f[x]);
}
int construct(std::vector<std::vector <int> > p) {
int n = p[0].size();
for(int i=0;i<n;i++)
{
f[i] = i;
}
bool flag = 1;
bool flagk = 1;
bool flagy = 1;
bool flagall = 1;
vector <vector<int> > ans;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(p[i][j] == 3)
{
return 0;
}
if(p[i][j]!=1)
{
flag = 0;
}
if(p[i][j] !=0&&p[i][j]!=1)
{
flagk = 0;
}
if(p[i][j]!=0 &&p[i][j]!=2)
{
if(i==j)continue;
flagy = 0;
}
if(p[i][j]!=0&&p[i][j]!=1&&p[i][j]!=2)
{
flagall = 0;
}
}
}
if(flag == 1) //that means all distance is 1;
{
for(int i=0;i<p[0].size()-1;i++)
{
checkx[i][i+1] = true;
checkx[i+1][i] = true;
}
}
else
{
if(flagk == 1)//that means all distance is 0 or 1;
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(find(i)!=find(j))
{
if(p[i][j] == 1)
{
int xx = find(i);
for(int kk=0;kk<n;kk++)
{
if(find(kk) == xx) //that means they are in the same group
{
if(p[xx][j]==0) //that means they can't go to each other,however their father can go to each other.it can't be implented
{
return 0;
break;
}
}
}
//if it hasn't return,that means it can be implented.
checkx[i][j] = true;
checkx[j][i] = true;
//and we should add the j in the same group;
f[find(j)] = find(i);
}
else
{
continue;
}
}
else//that means they are in the same set.
{
if(p[i][j] == 1)
{
continue;
}
else
{
if(p[i][j] == 0)
{
return 0;
break;
}
}
}
}
}
}
else
{
if(flagy == 1)//that means the distance are all 0 or 2;
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(find(i)!=find(j))
{
if(p[i][j] == 0)continue;
else//they have the way to go each other.
{
for(int kk=0;kk<n;kk++)
{
if(find(kk) == find(i))
{
if(p[kk][j] == 0)
{
return 0;
break;
}
}
}
}
f[find(j)] = find(i);
}
else //they means they have same father
{
if(p[i][j] == 0) //it is impossible
{
return 0;
break;
}
}
}
}
vector<int> nod[1005];
for(int i=0;i<n;i++)
{
int xx = find(i);
nod[xx].push_back(i);
}
for(int i=0;i<n;i++)
{
if(nod[i].size()!=0)
{
if(nod[i].size()==2)
{
return 0;
break;
}
else
{
for(int j=0;j<nod[i].size()-1;j++)
{
int xx = nod[i][j];
int yy = nod[i][j+1];
checkx[xx][yy]= true;
checkx[yy][xx] = true;
}
int m = nod[i].size();
int xx = nod[i][m-1];
int yy = nod[i][0];
checkx[xx][yy] = true;
checkx[yy][xx] = true;
}
}
}
}
else //that means they are all 0,1,2;
{
if(flagall == 1)
{
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(find(i)!=find(j))
{
if(p[i][j] == 0)continue;
//that means they are some ways to go.
for(int kk=0;kk<n;kk++)
{
if(find(kk) == find(i)) //that means they are in the same group
{
if(p[kk][j] == 0)
{
return 0;
break;
}
}
}
f[find(j)] = find(i);
}
else //that means they are in the same group
{
if(p[i][j] == 0) //that means they are in the same group,but no ways to go to each other
{
return 0;
break;
}
}
}
}
//and we can know the different kinds of node.
vector<int> nod[1005];
for(int i=0;i<n;i++)
{
int xx = find(i);
nod[xx].push_back(i);
}
//reset the merge and query set.
for(int i=0;i<n;i++)
{
f[i] = i;
}
vector<int> edge[1005];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
edge[j].clear();
}
if(nod[i].size() == 0||nod[i].size()==1)continue;
for(int j=0;j<nod[i].size();j++)
{
int xx = nod[i][j];
edge[xx].push_back(xx);
}
for(int j=0;j<nod[i].size();j++)
{
for(int k=j+1;k<nod[i].size();k++)
{
if(p[j][k] == 0)return 0;
else
{
if(find(j) !=find(k)) //that means they are not in the same edge.
{
if(p[j][k] == 1)
{
int temp = find(j);
for(int pp=0;pp<edge[temp].size();pp++)
{
if(p[pp][k] == 2)return 0;
}
edge[temp].push_back(k);
edge[k].pop_back();
checkx[j][k] = true;
checkx[k][j] = true;
f[find(k)] = find(j);
}
else//that means p[j][k] = 2
{
int temp = find(j);
for(int pp=0;pp<edge[temp].size();pp++)
{
if(p[pp][k] == 1) //if only one ways;
{
return 0;
}
}
}
}
else //they are in the same group
{
if(p[j][k] == 2)return 0; //in the same group ,there mustn't be two ways.
}
}
}
}
vector<int> pq;
//and, we have finished disclpined all of the edge.
pq.clear();
for(int j=0;j<n;j++)
{
if(edge[j].size()!=0)//it is for this set.
{
pq.push_back(edge[j][0]);
}
}
if(pq.size()==2)//that means the count of edge is 2
{
vector<int> x1;
for(int j=0;j<n;j++)
{
if(edge[j].size()!=0)
{
x1.push_back(j);
}
}
int k1 = x1[0];
int k2 = x1[1];
for(int j=0;j<edge[k1].size();j++)
{
for(int k=0;k<edge[k2].size();k++)
{
int fst = edge[k1][j];
int sd = edge[k2][k];
if(p[fst][sd] == 2)
{
return 0;
}
}
}
}
for(int j=0;j<pq.size()-1;j++)
{
int fst = pq[j];
int sd = pq[j+1];
checkx[fst][sd] = true;
checkx[sd][fst] = true;
}
int m = pq.size();
int fst = pq[0];
int sd = pq[m-1];
checkx[fst][sd] = true;
checkx[sd][fst] = true;
}
}
}
}
}
for(int i=0;i<p[0].size();i++)
{
vector<int> v;
for(int j=0;j<p[0].size();j++)
{
if(i==j)
{
v.push_back(0);
}
else
{
if(checkx[i][j] == true)
{
v.push_back(1);
}
else
{
v.push_back(0);
}
}
}
ans.push_back(v);
}
build(ans);
return 1;
}Compilation message (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... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||