Submission #28074

#	Time	Username	Problem	Language	Result	Execution time	Memory
28074		samir_droubi	KOVANICE (COI15_kovanice)	C++14	100 / 100	569 ms	24592 KiB

kovanice

#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 (stderr)

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40