oj.uz

Submission #28074

# Submission time Handle Problem Language Result Execution time Memory
28074 2017-07-15T08:08:16 Z samir_droubi KOVANICE (COI15_kovanice) C++14
100 / 100
 569 ms 24592 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m,v;
const int mxn=(3e5)+5;
vector<pair<int,int> >e;
int p[mxn];
int sz[mxn];

vector<int>gr[mxn];
int in[mxn];

int find(int x)
{
  if(x==p[x])return x;
  return p[x]=find(p[x]);
}
void merge(int x,int y)
{
  x=find(x);
  y=find(y);
  if(x==y)return;
  if(sz[x]>sz[y])swap(x,y);
  sz[y]+=sz[x];
  sz[x]=0;
  p[x]=y;
}

int vl[mxn];
queue<int>q;
void bfs()
{
  while(!q.empty())
  {
    int v=q.front();
    q.pop();
    for(int i=0;i<gr[v].size();++i)
    {
      int u=gr[v][i];
      --in[u];
      vl[u]=max(vl[u],vl[v]+1);
      if(in[u])continue;
      q.push(u);
    }
  }
}

bool ok[mxn];
bool vs[mxn];
void dfs(int v)
{
  if(vl[v]==n)ok[v]=true;
  vs[v]=true;
  for(int i=0;i<gr[v].size();++i)
  {
    int u=gr[v][i];
    if(!vs[u])dfs(u);
    if(vl[v]+1==vl[u])ok[v]|=ok[u];
  }
}
int main()
{
  scanf("%d%d%d",&n,&m,&v);
  for(int i=1;i<=m;++i)
  {
    p[i]=i;
    sz[i]=1;
  }
  for(int i=0;i<v;++i)
  {
    int x,y;
    char c;
    cin>>x>>c>>y;
    if(c=='=')merge(x,y);
    else e.push_back({x,y});
  }
  for(int i=0;i<e.size();++i)
  {
    int x=e[i].first;
    int y=e[i].second;
    ++in[find(y)];
    gr[find(x)].push_back(find(y));
  }
  for(int i=1;i<=m;++i)
  {
    if(i!=p[i])continue;
    if(in[i]==0)
    {
      vl[i]=1;
      q.push(i);
    }
  }
  bfs();
  for(int i=1;i<=m;++i)
  {
    if(i!=p[i])continue;
    if(vs[i])continue;
    dfs(i);
  }
  for(int i=1;i<=m;++i)
  {
    if(ok[find(i)])
      printf("K%d\n",vl[find(i)]);
    else puts("?");
  }
  return 0;
}

Compilation message

kovanice.cpp: In function 'void bfs()':
kovanice.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[v].size();++i)
                  ^
kovanice.cpp: In function 'void dfs(int)':
kovanice.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<gr[v].size();++i)
                ^
kovanice.cpp: In function 'int main()':
kovanice.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<e.size();++i)
                ^
kovanice.cpp:62:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&n,&m,&v);
                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14328 KB Output is correct
2 Correct 3 ms 14328 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 16636 KB Output is correct
2 Correct 139 ms 16768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15968 KB Output is correct
2 Correct 76 ms 15960 KB Output is correct
3 Correct 69 ms 15960 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 20740 KB Output is correct
2 Correct 453 ms 20288 KB Output is correct
3 Correct 486 ms 20284 KB Output is correct
4 Correct 519 ms 24576 KB Output is correct
5 Correct 569 ms 24592 KB Output is correct