oj.uz

Submission #241148

# Submission time Handle Problem Language Result Execution time Memory
241148 2020-06-23T06:26:00 Z computerbox KOVANICE (COI15_kovanice) C++14
60 / 100
 354 ms 56164 KB 
#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";


using namespace std;

ll n,m,k;
vector<ll>adj[300010];
vector<ll>adj1[300010];
vector<ll>adj2[300010];
ll dp[300010];
ll deg[300010];
ll color[300010];
vector<ll>tmp;
ll used[300010];
ll sig1[300010];
ll push[300010];


ll rankk[300010];
ll par[300010];


void make_set(ll n)
{
  for(ll i=1;i<=n;i++)rankk[i]=1,par[i]=i;	
}

ll findd(ll v)
{
  while(par[v]!=v)
  {
    par[v]=par[par[v]];
    v=par[v];  
  }	
  return v;
}

void make_union(ll a,ll b)
{
  a=findd(a);
  b=findd(b);
  if(a!=b)
  {
    if(rankk[a]>rankk[b])swap(a,b);  
	par[a]=par[b];
	rankk[b]+=rankk[a];
  }	  	  	
}

ll checkk(ll a,ll b)
{
  if(findd(a)!=findd(b))return 1;
  else return 0;	
}


vector<ll>tops;

void dfs(ll v)
{ 
  used[v]=1;
  for(auto to:adj1[v])
  {
    if(used[to]==0)
    {
	  dfs(to);	
    }  
  }	
  tops.pb(v);
}

void dfs1(ll v,ll sig)
{
  used[v]=1;
  sig1[v]=max(sig1[v],sig);
  
  for(auto to:adj1[v])
  {
	if(used[to]==0)
	{
	  dfs1(to,sig);	
    }  
    else
    {
	  push[to]=max(push[to],sig);	
    }
  }	
}

void dfs2(ll v)
{
  used[v]=1;
  sig1[v]=max(sig1[v],push[v]);
  
  for(auto to:adj1[v])
  {
	if(used[to]==0)
	{
	  push[to]=push[v];
	  dfs2(to);	
    }  
  }	
}

ll mx=0;
vector<ll>el;



vector< pair<ll,ll> >edges;


int main(){
FLASH;
cin>>n>>m>>k;
make_set(m);
for(ll i=1;i<=k;i++)
{
  string stroka;
  cin>>stroka;
  char sig;
  ll cis1=0,cis2=0;
  ll j=0;
  for(;j<(ll)stroka.size();j++)
  {
	if(isdigit(stroka[j]))cis1=(cis1*10+(stroka[j]-'0'));
	else break;  
  }
  sig=stroka[j];
  j++;
  for(;j<(ll)stroka.size();j++)
  {
	if(isdigit(stroka[j]))cis2=(cis2*10+(stroka[j]-'0'));
	else break;  
  }

  if(sig=='=')
  {
	make_union(cis1,cis2);  
  }
  else edges.pb(mp(cis1,cis2));
  
}

for(auto i:edges)
{
  ll cis1=i.first;
  ll cis2=i.second;
  cis1=findd(cis1);
  cis2=findd(cis2);
  adj1[cis1].pb(cis2);
  adj2[cis2].pb(cis1);	
  deg[cis2]++;
}


for(ll i=1;i<=m;i++)
{
  if(used[findd(i)]==0)dfs(findd(i));	
}


for(ll i=1;i<=m;i++)dp[i]=1;

for(auto i:tops)
{
  for(auto j:adj2[i])
  {
	dp[j]=max(dp[j],dp[i]+1);  
  }	
}

memset(used,0,sizeof(used));

for(ll i=1;i<=m;i++)
{
  if(used[findd(i)]==0 && (ll)adj1[findd(i)].size()!=0 && deg[findd(i)]==0)
  {
	if(dp[findd(i)]==n)dfs1(findd(i),1);
	else dfs1(findd(i),0);  
  }
}

memset(used,0,sizeof(used));

for(ll i=1;i<=m;i++)
{
  if(used[findd(i)]==0 && (ll)adj1[findd(i)].size()!=0 && deg[findd(i)]==0)
  {
	dfs2(findd(i));
  }
}

memset(used,0,sizeof(used));

for(ll i=1;i<=m;i++)
{
  if(sig1[findd(i)]==1 || push[findd(i)]==1)
  {
	color[findd(i)]=n-dp[findd(i)]+1;  
  }	
  else color[findd(i)]=0;
}



for(ll i=1;i<=m;i++)
{
 if(color[findd(i)]==0)cout<<"?"<<endl;
 else cout<<"K"<<color[findd(i)]<<endl;	
}





return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24064 KB Output is correct
2 Correct 20 ms 23936 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 40296 KB Output is correct
2 Correct 151 ms 40680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 27636 KB Output is correct
2 Correct 35 ms 27636 KB Output is correct
3 Correct 35 ms 27636 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 354 ms 56164 KB Output isn't correct
2 Halted 0 ms 0 KB -