Submission #28073

#TimeUsernameProblemLanguageResultExecution timeMemory
28073samir_droubiKOVANICE (COI15_kovanice)C++14
60 / 100
519 ms20740 KiB
#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); 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:34: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:51: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:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<e.size();++i)
                ^
kovanice.cpp:60: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);
                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...